1
формально, скажем, у нас есть 2 мешка с емкостью c1 и c2. Есть N позиций с прибылью pi и весами wi. Как и в задаче 0-1 Knapsack, нам нужно заполнить c1 и c2 этими элементами таким образом, чтобы максимальная прибыль была максимизирована. Предположим, что pi и wi - целые положительные числа!алгоритм для рюкзака 0-1 с двумя мешками?
Для проблемы с 2 рюкзаком ниже рекуррентное отношение выполняется хорошо?
DP [I] [J] [K] максимальная прибыль, которую мы могли бы достичь от первых предметов i, так что вес точно j использовался в рюкзаке №1, а вес точно k использовался в рюкзаке №2
DP [i] [j] [k] = max (DP [i-1] [j] [k], DP [i] [j-1] [k], DP [i] [j] [k-1], DP [i] [jW [j]] [k] + C [i], DP [i] [j] [kW [k]] + C [i])
вопрос не в том, чтобы переписать уравнение, но сообщите мне, если ниже неправильно? DP [i] [j] [k] = max (DP [i-1] [j] [k], DP [i] [j-1] [k], DP [i] [j] [k- 1], DP [i] [jW [j]] [k] + C [i], DP [i] [j] [kW [k]] + C [i]) –
Ваше уравнение, скорее всего, неверно. Пожалуйста, ознакомьтесь с http://en.wikipedia.org/wiki/Knapsack_problem, чтобы понять, как вывести уравнение рекурсии для проблемы с рюкзаком 0/1 с одним рюкзаком. Как только вы поймете принцип принятия рекуррентного уравнения для этой базовой проблемы, вы можете вывести правильное уравнение для проблемы с рюкзаком с двумя рюкзаками. – ysrhung
Должно быть 3 отдельных случая: (1) элемент i не помещается в оба рюкзака, (2) элемент i помещается в рюкзак 1 и (3) элемент i помещается в рюкзак 2. Таким образом, должно быть 3 случая. В качестве примера возьмем случай (3), значение case (3) должно быть DP [i-1] [j] [kW [i]] + C [i], так как емкость ранца 2 уменьшается на W [i] и значение увеличивается на c [i]. Примечание: элемент i рассматривается и, следовательно, должен быть чем-то вроде «DP [i-1] .....» Вот почему ваше уравнение выглядит неправильно. – ysrhung