# 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