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

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

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

mattbuell, в 03:54 (источник)

1 ответ

  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]

    Есть много библиотек решателей, которые решат эту программу для вас; в качестве альтернативы, вы можете сделать ветку и связать себя. Вот двойная линейная программа, которая может быть решена для получения верхней границы на целочисленной целевой программе, которая необходима для ветви и границы.

    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).