0/1 背包算法的变体

Question

我是编程新手，被要求解决一个工作程序。现在我们正在处理一个典型的 0/1 背包问题，其中 benefit/value 在给定质量和体积约束的情况下最大化。

我的任务是基本上扭转这一局面，并在给定值约束的情况下最小化体积或质量。换句话说，我希望我的收益分数大于或等于一个设定值，然后看看在给定该阈值的情况下我能得到多小的背包。

我曾尝试在其他地方研究这个问题，并确信它可能有一个正式名称，但我找不到它。如果有人有任何信息，我将不胜感激。我有点不知道如何解决这种类型的算法，因为您不能使用相同的递归公式。

Answer 1

我们称物品i的重量为w(i)，其价值为v(i)。任意排序物品，并定义 f(i, j) 为背包的最小可能容量，该背包可容纳前 i 件物品的子集，总计至少为 j 的值。

为了计算f(i, j)，我们可以把第i个物品放在背包里，也可以不放在背包里，所以

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)) 只是确保在 v(i) > j.[=16= 的情况下，f() 的递归调用中的第二个参数不会为负数]

Memoising 这给出了伪多项式 O(nc)-时间，O(nc)-space 算法，其中 n 是项目数，c 是值阈值。您可以通过以自下而上的方式计算它来节省 space（可能还有时间，尽管不是在渐近意义上）——这会将 space 复杂度降低到 O(c)，因为在计算时f(i, ...) 您只需要访问 f(i-1, ...)，因此您只需要保留 DP 矩阵的先前和当前 "rows"。

Answer 2

如果我对你的问题理解正确，你希望解决的问题在表格中：

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

这是一个有 3 个约束条件的背包问题。通过设置 x_i = 1 - y_i.

，解决方案 y 可以很容易地转换为原始问题的等效解决方案

0/1 背包算法的变体

Variation on 0/1 Knapsack Algorithm

algorithm

matlab

logic

knapsack-problem

dynamic-programming