Data Structures Algorithms 简明教程
0-1 Knapsack Problem
我们在本教程的前文中使用贪婪算法讨论了分数背包问题。它表明，贪婪算法为分数背包提供了最优解。但是，本章将使用动态规划方法介绍 0-1 背包问题及其分析。
与分数背包不同，物品始终全部存储，而不会使用它们的零分数部分。它要么添加到背包中，要么不添加。这就是为什么这种方法称为* 0-1 背包问题* 的原因。
因此，对于 0-1 背包来说， xi 的值可以是 0 也可以是 1 ，而其他约束保持不变。
0-1 背包不能通过贪婪算法解决。贪婪算法不能保证这种方法的最优解。在许多情况下，贪婪算法可能会给出一个最优解。
0-1 Knapsack Algorithm
Problem Statement 一名窃贼正在抢劫一家商店，并且最多可以携带 W 的重量进入他的背包中。共有 n 件物品，第 i 件物品的重量为 wi，选择该物品的利润为 pi 。窃贼应拿走哪些物品？
设 i 为 W 美元的最佳解决方案 S 中编号最高的物品。则 S’ = S − {i} 是 W – wi 美元的最佳解决方案，并且解决方案 S 的值为 Vi 加上子问题的价值。
我们可以使用以下公式表示此事实：定义 c[i, w] 为物品 1,2, … , i 和最大重量 w 的解决方案。
该算法采用以下输入
-
The maximum weight W
-
物品数目 n
-
两个序列 v = <v1, v2, …, vn> and w = <w1, w2, …, wn>
可以从表格中推导可获取的项目集合，从 c[n, w] 开始并向后追溯，找出最佳值来源。
如果 c[i, w] = c[i-1, w] ，则项目 i 不是解决方案的一部分，并且我们继续使用 c[i-1, w] 追溯。否则，项目 i 是解决方案的一部分，并且我们继续使用 c [i-1, w-W] 追溯。
Dynamic-0-1-knapsack (v, w, n, W)
for w = 0 to W do
c[0, w] = 0
for i = 1 to n do
c[i, 0] = 0
for w = 1 to W do
if wi ≤ w then
if vi + c[i-1, w-wi] then
c[i, w] = vi + c[i-1, w-wi]
else c[i, w] = c[i-1, w]
else
c[i, w] = c[i-1, w]以下示例将建立我们的声明。
Solution
使用 0-1 背包的贪婪方法，储存在背包中的重量将为 A+B = 4，最大利润为 2 + 4 = 6。但是，该解决方案不是最优解决方案。
因此，必须采用动态规划来解决 0-1 背包问题。
Step 1
构建邻接表，背包的最大重量为行，而项目分别以重量和利润为列。
要存储在表中的值是重量不超过背包的最大重量的项目的累积利润（每行的指定值）
因此，我们在第 0 行和第 0 列添加零，因为如果项目的重量为 0，则它的重量为零；如果背包的最大重量为 0，则不能将任何项目添加到背包中。
其余值填充为相对于项目和可储存在背包中的每列重量能获得的最大利润。
存储利润值的公式为：
c\left [ i,w \right ]=max\left\{c\left [ i-1,w-w\left [ i \right ] \right ]+P\left [ i \right ] \right\}
使用该公式计算所有值，获得的表为：
要找到要添加到背包中的项目，请从表中识别最大利润并识别构成利润的项目，在本例中为 {1, 7}。
最优解为 {1, 7}，最大利润为 12。