Рюкзак: одно ограничение, каждый элемент может быть выбран только один раз, с большим количеством элементов

Question

Я пишу алгоритм, принимающий форму проблемы с рюкзаком. Я пытаюсь максимизировать значение (V) моего рюкзака при максимальном весе (W). Уловы в том, что каждый элемент (I) можно выбрать только один раз, рюкзак, независимо от веса, может содержать только 10 предметов, а также очень большое количество предметов (500+).

Мои мысли до сих пор заключались в том, чтобы создать рюкзак с избыточным весом и рекурсивно работать назад, заменяя предметы по одному, пока он не станет < = максимальный вес. Это не проблема для создания наиболее оптимального ранца, однако я бы очень хотел создать следующие 100 или около того ранцев. Я думал, что смогу это сделать, продолжая рекурсивный процесс, однако я не чувствую, что это абсолютно точно, так как может отсутствовать несколько более оптимальные ранцы.

Answer 1

Эта проблема может быть сформулирована как целая программа.

maximize sum_{i in items} v_i * x_i 
subject to 
sum_{i in items} x_i <= 10  [u] 
sum_{i in items} w_i * x_i <= W [z] 
for all i in items, x_i in {0, 1} [y_i] 

Существует много библиотек-решателей, которые будут решать эту программу для вас; В качестве альтернативы вы можете сами сделать branch and bound. Вот двойственная линейная программа, которую можно решить, чтобы получить верхнюю границу объектного значения целочисленной программы, которая необходима для ветви и границы.

minimize 10 * u + W * z + sum_{i in items} y_i 
subject to 
for all i in items, u + w_i * z + y_i >= v_i [x_i] 
u >= 0 
z >= 0 
for all i in items, y_i >= 0 

Учитывая значение для z, установки других переменных является вопросом присвоения положительного y_i к девяти верхним элементам с помощью v_i - w_i * z при назначении u быть десятым наибольшим значением. Должна быть возможность тройного поиска z во времени O(n log n).