0-1背包问题

• 给你一组n个项目供你选择。
• 这些物品都有重量w₁，w₂、……w_n和价值观v₁，v₂、……v_n．
• 你有一个最大重量容量为C的集装箱。
• 您的目标是选择具有最大价值且总重量不超过容器容量的物品子集。

一个指数级大的搜索空间

• 搜索空间是列表{1,2，…，n}的赢博体育可能子集的空间
• 有2n个可能的子集要搜索。
• 幸运的是，在搜索空间中有很多冗余。
• 例如，无论您是否决定将项目n放入容器中，您都必须考虑列表{1,2，…，n-1}的赢博体育可能子集。

最优子集属性

最优子集的性质是说最优解的任何子集也是最优的。

例如，假设{i1， i2，…，ik}是总价值为V的最优子集中项目的索引列表。子列表{i1， i2，…，ik-1}的总价值为V - vik，将适合容量为C - wik的容器。最优子集属性表示，除了项目ik之外的原始项目集合中，没有其他适合容量为C - vik的容器的子集的值大于V - vik。

这个证明是一个简单的反证法。如果我们能够找到一个更好的子集，我们可以简单地将原始解决方案中的i1， i2，…，ik-1项替换为该子集，从而在不超过容器容量的情况下获得比原始解决方案更高的总价值。这与原始解是最优解的说法相矛盾。

递归解决方案

• 为了构造一个最优子集，我们必须对列表中的项目{1,2，…，n}做出一系列选择。
• 对于每个项目，我们必须检查两个选项：拿走项目或留下项目。
• 如果我们取一件物品，我们要把它的价值加到总数中，但我们也要把容器的容量减去我们加进去的物品的重量。
• 我们使用last-rest递归以相反的顺序处理列表。
• 递归中的基本情况出现在没有更多项目可供选择的情况下。这种情况的值是0。

递归的伪代码

假设V (1 . .n]是一个数值数组，W[1..]N]是一个权重数组。

函数maxValue（k,c）计算容量为c的背包中可以携带的最大值，如果您只能从物品1..k中进行选择。

maxValue(k,c) if k == 0 return 0 max = maxValue(k-1,c) if W[k] <= c and maxValue(k-1,c-W[k])+V[k] > max = maxValue(k-1,c-W[k])+V[k] return max

递归的基本思想是，对于可能物品列表中的每个物品k，我们必须决定是否打包该物品。递归代码查看两个选项，不取项和取项，并确定这两个选项中哪一个产生更大的值。如果你决定拿这个东西，你首先要确定它是否适合你的容器。

memoize的版本

假设V (1 . .n]是一个数值数组，W[1..]N]是一个权重数组。

函数maxValue（k,c）计算容量为c的背包中可以携带的最大值，如果您只能从物品1..k中进行选择。

二维数组M[0..n,0..C]存储我们找到的最大值。开始时，该数组的赢博体育项都初始化为0。

maxValue(k,c)
  if M[k,c] > 0 return M[k,c]
  if k == 0 return 0
  max = maxValue(k-1,c)
  if W[k] <= c and maxValue(k-1,c-W[k])+V[k] > max
    max = maxValue(k-1,c-W[k])+V[k]
  M[k,c] = max
  return max

动态规划版本

动态规划版本是对记忆版本的直接翻译。

maxValue（cap）让M[0..n,0..]如果W[row] <= c且M[row-1，c-W[row]] + V[row] > M[row,c] = M[row-1,c-W]] = M[row,c] = M[row,c]] = M[row,c] = M[row，c]] + V[row]返回M[n，cap]

在设置这段代码时，我们只需要注意一件事。我们需要确保在使用表中的值时，我们已经填充了该值。

该算法处理这个问题的方法是，首先用基本情况填充表的第0行，然后向下处理表的行。代码只使用来自前几行的值，所以我们是安全的。

最后一个问题

动态规划解可以告诉我们可以执行的最大值，但它不能直接告诉我们应该把哪一组项放在子集中。这个问题的解决方法相对简单。我们引入第二个二维数组T[0..n,0..C]，它存储关于是否取项的决定。如果我们考虑是否将物品k放入容量最大的容器c中，我们将我们的决定存储在T[k，c]中。

maxValue（cap）让M[0..n,0..]设T[0..n,0..]对于c = 0到M[0，c] = 0, T[0,c] = False，对于row = 1到n，对于c = 0到M[row，c] = M[row, 1,c] T[row,c] = False，如果W[row] <= c和M[row-1，c-W[row]] + V[row] > M[row,c] M[row,c] = M[row, 1,c-W[row]] + V[row] T[row,c] = True返回M[n，cap]

然后，我们使用存储在第二个表中的值来构造并打印最优解：

printOptimal(k,c) == True if T[k,c] == True printOptimal（k,c]) == True printOptimal(k-1,c]) + ": " + V[k]）

为了打印最优解中的项目列表，我们调用printOptimal（n，C）。