# 0-1 背包问题

+----------+---+---+---+---+
|   Item   | 1 | 2 | 3 | 4 |
+----------+---+---+---+---+
|  Weight  | 1 | 3 | 4 | 5 |
+----------+---+---+---+---+
|   Value  | 1 | 4 | 5 | 7 |
+----------+---+---+---+---+


• 我们可以使用较少的项目并计算使用这些项目可以获得的最大值并将它们组合起来。所以我们的问题可以分为子问题。
• 如果我们计算项 {1,2} 的组合，我们可以在计算 { 1,2,3} 时使用它。
• 如果我们最小化重量并使价值最大化，我们可以找到最佳解决方案。

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+


+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+


if weight[i] > j
Table[i][j] := Table[i-1][j]
end if


• 我们选择该项目并使用我们在获取此项目后可从其他剩余项目获得的最大值添加其值。
• 我们可以排除这个项目。

if weight[i] <= j
w := weight[i]
Table[i][j] := max(w + Table[i][j-w], Table[i-1][j])
end if


+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+


Procedure Knapsack(Weight, Value, maxCapacity):
n := Item.size - 1
Table[n+1][maxCapacity+1]
for i from 0 to n
Table[i][0] := 0
end for
for j from 1 to maxCapacity
if j >= Weight[0]
Table[0][j] := Weight[0]
else
Table[0][j] := 0
end if
end for
for i from 1 to n
for j from 1 to maxCapacity
if Weight[i] >= j                                            //can't pick the item
Table[i][j] := Table[i-1][j]
else                                                        //can pick the item
w := Weight[i]
Table[i][j] := max(w + Table[i-1][j-w], Table[i-1][j])
end if
end for
end for
Return Table[n][maxCapacity]


• 对于任何项目，如果值来自上面的位置，我们没有采取当前项目。我们走了一步。
• 如果价值不是来自上面的位置，我们就拿走了这个项目。所以我们走上一步，x 退后一步，其中 x 是当前项目的权重。

Procedure printItems(Table, maxCapacity, Value):
i := Item.size - 1
j := maxCapacity
while j is not equal to 0
if Table[i][j] is equal to Table[i-1][j]
i := i - 1
else
Print: i
j := j - weight[i]
i := i - 1
end if
end while


https://i.stack.imgur.com/UrImV.jpg