Data Structures Algorithms 简明教程
0-1 Knapsack Problem
我们在本教程的前文中使用贪婪算法讨论了分数背包问题。它表明，贪婪算法为分数背包提供了最优解。但是，本章将使用动态规划方法介绍 0-1 背包问题及其分析。
We discussed the fractional knapsack problem using the greedy approach, earlier in this tutorial. It is shown that Greedy approach gives an optimal solution for Fractional Knapsack. However, this chapter will cover 0-1 Knapsack problem using dynamic programming approach and its analysis.
与分数背包不同，物品始终全部存储，而不会使用它们的零分数部分。它要么添加到背包中，要么不添加。这就是为什么这种方法称为* 0-1 背包问题* 的原因。
Unlike in fractional knapsack, the items are always stored fully without using the fractional part of them. Its either the item is added to the knapsack or not. That is why, this method is known as the* 0-1 Knapsack problem*.
因此，对于 0-1 背包来说， xi 的值可以是 0 也可以是 1 ，而其他约束保持不变。
Hence, in case of 0-1 Knapsack, the value of xi can be either 0 or 1, where other constraints remain the same.
0-1 背包不能通过贪婪算法解决。贪婪算法不能保证这种方法的最优解。在许多情况下，贪婪算法可能会给出一个最优解。
0-1 Knapsack cannot be solved by Greedy approach. Greedy approach does not ensure an optimal solution in this method. In many instances, Greedy approach may give an optimal solution.
0-1 Knapsack Algorithm
Problem Statement 一名窃贼正在抢劫一家商店，并且最多可以携带 W 的重量进入他的背包中。共有 n 件物品，第 i 件物品的重量为 wi，选择该物品的利润为 pi 。窃贼应拿走哪些物品？
Problem Statement − A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are n items and weight of ith item is wi and the profit of selecting this item is pi. What items should the thief take?
设 i 为 W 美元的最佳解决方案 S 中编号最高的物品。则 S’ = S − {i} 是 W – wi 美元的最佳解决方案，并且解决方案 S 的值为 Vi 加上子问题的价值。
Let i be the highest-numbered item in an optimal solution S for W dollars. Then S’ = S − {i} is an optimal solution for W – wi dollars and the value to the solution S is Vi plus the value of the sub-problem.
我们可以使用以下公式表示此事实：定义 c[i, w] 为物品 1,2, … , i 和最大重量 w 的解决方案。
We can express this fact in the following formula: define c[i, w] to be the solution for items 1,2, … , i and the maximum weight w.
该算法采用以下输入
The algorithm takes the following inputs
-
The maximum weight W
-
The number of items n
-
The two sequences v = <v1, v2, …, vn> and w = <w1, w2, …, wn>
可以从表格中推导可获取的项目集合，从 c[n, w] 开始并向后追溯，找出最佳值来源。
The set of items to take can be deduced from the table, starting at c[n, w] and tracing backwards where the optimal values came from.
如果 c[i, w] = c[i-1, w] ，则项目 i 不是解决方案的一部分，并且我们继续使用 c[i-1, w] 追溯。否则，项目 i 是解决方案的一部分，并且我们继续使用 c [i-1, w-W] 追溯。
If c[i, w] = c[i-1, w], then item i is not part of the solution, and we continue tracing with c[i-1, w]. Otherwise, item i is part of the solution, and we continue tracing with 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]以下示例将建立我们的声明。
The following examples will establish our statement.
Example
让我们考虑背包容量为 W = 8，并且项目如以下表格所示。
Let us consider that the capacity of the knapsack is W = 8 and the items are as shown in the following table.
Solution
使用 0-1 背包的贪婪方法，储存在背包中的重量将为 A+B = 4，最大利润为 2 + 4 = 6。但是，该解决方案不是最优解决方案。
Using the greedy approach of 0-1 knapsack, the weight that’s stored in the knapsack would be A+B = 4 with the maximum profit 2 + 4 = 6. But, that solution would not be the optimal solution.
因此，必须采用动态规划来解决 0-1 背包问题。
Therefore, dynamic programming must be adopted to solve 0-1 knapsack problems.
Step 1
Step 1
构建邻接表，背包的最大重量为行，而项目分别以重量和利润为列。
Construct an adjacency table with maximum weight of knapsack as rows and items with respective weights and profits as columns.
要存储在表中的值是重量不超过背包的最大重量的项目的累积利润（每行的指定值）
Values to be stored in the table are cumulative profits of the items whose weights do not exceed the maximum weight of the knapsack (designated values of each row)
因此，我们在第 0 行和第 0 列添加零，因为如果项目的重量为 0，则它的重量为零；如果背包的最大重量为 0，则不能将任何项目添加到背包中。
So we add zeroes to the 0th row and 0th column because if the weight of item is 0, then it weighs nothing; if the maximum weight of knapsack is 0, then no item can be added into the knapsack.
其余值填充为相对于项目和可储存在背包中的每列重量能获得的最大利润。
The remaining values are filled with the maximum profit achievable with respect to the items and weight per column that can be stored in the knapsack.
存储利润值的公式为：
The formula to store the profit values is −
c\left [ i,w \right ]=max\left\{c\left [ i-1,w-w\left [ i \right ] \right ]+P\left [ i \right ] \right\}
使用该公式计算所有值，获得的表为：
By computing all the values using the formula, the table obtained would be −
要找到要添加到背包中的项目，请从表中识别最大利润并识别构成利润的项目，在本例中为 {1, 7}。
To find the items to be added in the knapsack, recognize the maximum profit from the table and identify the items that make up the profit, in this example, its {1, 7}.
最优解为 {1, 7}，最大利润为 12。
The optimal solution is {1, 7} with the maximum profit is 12.