Вариация на алгоритм ранжирования 0/1

Question

Я очень новичок в программировании, и мне было предложено решить программу для работы. Сейчас мы имеем дело с типичной проблемой 0/1 Knapsack, в которой преимущество/значение максимизируется с учетом ограничений массы и объема.

Моя задача состоит в том, чтобы в принципе обратить вспять это и свести к минимуму либо объем, либо массу, заданные для ограничения значения. Другими словами, я хочу, чтобы мой показатель эффективности был больше или равен установленному значению, а затем посмотрел, насколько мал я могу получить рюкзак, учитывая это пороговое значение.

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

Answer 1

Если я правильно понимаю ваш вопрос, проблема, которую Вы хотите решить на форме:

let mass_i be the mass of item i, let vol_i the volume, and let val_i be its value. 
Let x_i be a binary variable, where x_i is one if and only if the item is in the knapsack. 

minimize (mass_1 * x_1 + ... + mass_n * x_n) //The case where you are minimizing mass 
s.t. mass_1 * x_1 + ... + mass_n * x_n >= MinMass 
     vol_1 * x_1 + ... + vol_n * x_n >= MinVolume 
     val_1 * x_1 + ... + val_n * x_n >= MinValue 
     x_i in {0,1} for all i 

трюк вы можете использовать, чтобы сделать его более «knapsacky» является замена x_i с 1-y_i, где y_i - 1 единица, если и только если пункт i - не в рюкзаке. Затем вы получите эквивалентную проблему по форме:

let mass_i be the mass of item i, let vol_i the volume, and let val_i be its value. 
Let y_i be a binary variable, where y_i is one if and only if the item is NOT in the knapsack. 

maximize mass_1 * y_1 + ... + mass_n * y_n) //The case where you are minimizing mass 
s.t. mass_1 * y_1 - ... + mass_n * y_n <= mass_1 + ... + mass_n - MinMass 
     vol_1 * y_1 - ... + vol_n * y_n <= vol_1 + ... + vol_n - MinVolume 
     val_1 * y_1 - ... + val_n * y_n <= val_1 + ... + val_n - MinValue 
     y_i in {0,1} for all i 

, который является проблемой ранца с тремя ограничениями. Решение y может быть легко преобразовано в эквивалентное решение для вашей исходной проблемы, установив x_i = 1 - y_i.

Answer 2

Назовем вес элемента i w (i) и его значение v (i). Закажите элементы произвольно и определите f (i, j) как минимальную возможную емкость рюкзака, который содержит подмножество первых элементов i, суммирующих по крайней мере значение j.

Для вычисления F (I, J), мы можем либо включить пункт-ю или не в рюкзаке, так

f(i>0, j>0) = min(g(i, j), h(i, j))  # Can include or exclude ith item; pick the best 
f(_, 0) = 0        # Don't need any capacity to reach value of 0 
f(i<=0, j>0) = infinity     # Can't get a positive value with <= 0 items 

g(i, j) = f(i-1, j)      # Capacity needed if we exclude ith item 
h(i, j) = f(i-1, max(0, j-v(i))) + w(i) # Capacity needed if we include ith item 

В последней строке, max(0, j-v(i)) просто убеждается, что второй аргумент в рекурсивной звонок в f() не идет отрицательным в случае, если v(i) > j.

Запоминающее это дает псевдополиномиальный O (nc) -time, O (nc) -пространственный алгоритм, где n - количество элементов, а c - порог значения. Вы можете сэкономить место (и, возможно, время, хотя и не в асимптотическом смысле), вычислив его снизу вверх - это приведет к уменьшению сложности пространства до O (c), поскольку при вычислении f(i, ...) вам нужен только доступ к f(i-1, ...) , поэтому вам нужно сохранить только предыдущие и текущие «строки» матрицы DP.