Максимизация рюкзака с дополнительными ограничениями

Question

Старая и известная проблема Рюкзак требует, чтобы с учетом емкости С и списка из n элементов {I_1, I_2, ..., I_n} с каждым значением I_j = (weight_j, value_j) максимизируйте значение при заполнении рюкзака.

Но что произойдет, если мы добавим ограничение,

1) число раз конкретный элемент выбран должен быть либо 0, либо должно быть нечетным (например: не может принимать только либо не 10lb гири или 1 , 3, 5, .. их число). 2) C = n^2 и n < = weight_j < = n^2 для всех j.

Какая реализация динамического программирования может использоваться для обработки дополнительных ограничений?

Некоторые советы были бы очень благодарны за то, как начать. Благодаря!

Answer 1

Вы можете сформулировать это вариант задачи о рюкзаке как Integer программы проблемы

Стандартный ранце:

Maximize sum(j) Value_j x X_j 
subject to 
     sum(j) Wt_j x X_j <= C 
     X_j is integer 

В вашем варианте X_j может принимать только различные значения: {0, 1,3,5, ...}

Формулирование ограничения для ограничения X на нечетные значения

Всякий раз, когда существуют эти ограничения на значения, которые может принимать переменная, введите переменные 0/1 для обработки этих условий.

Для каждого элемента j давайте представим кучу двоичных переменных Y и пару новых ограничений.

X_j - 1 Y_j1 - 3 Y_j3 - 5 Y_j5 ... - M Y_jm = 0 

m - наибольшее значение (нечетное число), которое может принимать Xj.

И ограничить X_j предположить одно из этих значений, мы добавим

Y_j0 + Y_j1 + Y_j3 + ... + Y_jm = 1 for each item j 
Y_j0, Y_j1, Y_j3 ..., Y_jm are {0,1} (binary) 

Переменная Y_j0 это позволить X_j взять на значение 0.

Тот факт, что C = n^2 гарантирует, что мы можем придумайте разумные верхние пределы m для каждого ограничения.

Теперь вы можете решить этот модифицированный рюкзак с помощью целочисленного программирования. Он по-прежнему будет искать элементы в порядке убывания «плотности значений» (значение на килограмм), а ограничения, ограничивающие его нечетными значениями, будут использоваться для определенных граничных условий.

Надеюсь, что это поможет.

Answer 2

Проблема с рюкзаком представляет собой задачу целочисленного программирования, которая в своей простейшей форме может быть решена посредством динамического программирования. Даже, казалось бы, небольшие изменения в проблеме усложняют и гораздо лучше подходят для других подходов. Самый простой подход заключается в том, чтобы расслабить его до ряда линейных программ, используя ветку и связавшись с вами через возможные решения. Можно также использовать плоскость резки, но людям обычно легче понять и внедрить Branch and Bound. Посмотрите здесь http://mat.gsia.cmu.edu/orclass/integer/integer.html (проще, доступнее) http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf (более полный)