0-1 揹包問題

假設你被問到，考慮到你可以隨身攜帶揹包的總重量以及一些帶有重量和價值的物品，你怎麼能以這樣的方式取出這些物品，使得它們的價值總和最大，但是它們的重量總和不是超過你可以攜帶的總重量？在 0-1 指示任你挑選的專案，或者你沒有。我們每個專案都有一個數量。這意味著，你無法拆分該專案。如果它不是 0-1 揹包問題，那意味著如果你可以拆分專案，那就有一個貪婪的解決方案，這稱為分數揹包問題。

現在，讓我們專注於手頭的問題。例如，假設我們的揹包容量為 7 。我們有 4 個專案。他們的權重和值是：

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

一種蠻力方法將採用所有可能的專案組合。然後我們可以計算出它們的總重量，並將它們排除在超出我們揹包容量的範圍內，並找出能給我們帶來最大價值的那個。對於 4 個專案，我們需要檢查（ 4！ - 1 ）= 23 種可能的組合（不包括沒有專案的組合）。當專案數量增加時，這非常麻煩。在這裡，我們可以注意到的幾個方面，即：

• 我們可以使用較少的專案並計算使用這些專案可以獲得的最大值並將它們組合起來。所以我們的問題可以分為子問題。
• 如果我們計算項 {1,2} 的組合，我們可以在計算 { 1,2,3} 時使用它。
• 如果我們最小化重量並使價值最大化，我們可以找到最佳解決方案。

出於這些原因，我們將使用動態程式設計來解決我們的問題。我們的策略是：每當有新商品出現時，我們會檢查是否可以選擇商品，我們會再次選擇能夠帶來最大價值的商品。現在，如果我們選擇專案，我們的價值將是專案的價值，加上我們可以通過從我們的產能中減去價值以及我們可以獲得的剩餘重量的最大值來獲得的價值。如果我們不選擇該專案，我們將選擇能夠在不包含該專案的情況下為我們提供最大價值的專案。讓我們嘗試用我們的例子來理解它：

我們將採用一個二維陣列表，其中列數將是我們可以通過取專案+ 1 獲得的最大值。行數將與專案數相同。我們的陣列看起來像：

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

為方便起見，我們將每個專案的重量和價值合併到陣列中。請記住，這些不是陣列的一部分，這些僅用於計算目的，你不需要將這些值儲存在表陣列中。

我們的第一列填充 0 。這意味著如果我們的最大容量為 0 ，無論我們擁有什麼專案，因為我們無法選擇任何專案，我們的最大值將為 0 。讓我們從表[0] [1]開始。當我們填寫表[1] [1]時，我們問自己我們的最大容量是否為 1 而我們只有第一項，我們的最大值是多少？我們所能做的最好的就是 1 ，選擇專案。對於表[0] [2] ，這意味著如果我們的最大容量是 2 並且我們只有第一個專案，我們可以得到的最大值是 1 。對於表[0] [3] ，這將是相同的，表[0] [4] ，表[0] [5] ，表[0] [6] 和表[0] [7] 。這是因為我們只有一個專案，它給我們的價值 1 。由於我們每個專案只有 1 個數量，無論我們如何增加揹包的容量，從一個專案， 1 是我們可以做出的最佳價值。所以我們的陣列看起來像：

+-------+--------+---+---+---+---+---+---+---+---+
| `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 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

繼續，對於表[1] [1] ，我們問自己，如果我們有第 1 項和第 2 項，如果揹包的最大容量是 1 ，那麼我們可以獲得的最大值是多少？如果我們同時採用第 1 項和第 2 項，總重量將為 4 ，這將超過我們目前的揹包容量。因此無法選擇第 2 項。現在，如果不考慮第 2 項，我們能做的最好的事情是什麼？從頂部開始的值，即 Table [0] [1] ，它包含我們可以獲得的最大值，如果我們有最大容量 1 並且我們沒有選擇第二項。對於表[1] [2] ，因為 2 小於重量[2] ，即第二項的重量，我們不能拿該項。因此，我們可以確定，如果當前專案的權重大於我們的最大容量，我們就不能接受該專案。在這種情況下，我們只需從頂部取值，它代表我們可以採取的除專案之外的最大值。

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

現在對於**表[1] [3]，**因為我們的最大容量等於我們當前的重量，我們有兩個選擇。

• 我們選擇該專案並使用我們在獲取此專案後可從其他剩餘專案獲得的最大值新增其值。
• 我們可以排除這個專案。

在這兩個選擇中，我們將選擇一個可以獲得最大價值的選擇。如果我們選擇專案，我們得到：此專案的值+取得此專案後其餘專案的最大值= 4 + 0 = 4 。我們得到 4 從我們（的專案值） 重量陣列和 0 （我們可以從專案的其餘部分採取這一專案後，獲得最大價值）來通過去 1 個上面的步驟和 3 步回來。那是表[0] [0] 。為什麼？如果我們採取該專案，我們的剩餘容量將是 3 - 3 = 0 ，剩餘專案將是第一項。好吧，如果你還記得表[0] [0] 儲存我們可以獲得的最大值，如果我們的容量為 0 並且我們只有第一項。現在，如果我們不選擇專案，我們可以獲得的最大值來自上面的 1 步，即 1 。現在，我們取最大值這兩個值的（ 4 ， 1 ），並設定表[1] [2] = 4 。對於表[1] [4] ，從 4 開始，最大揹包容量大於 3 ，即我們當前專案的重量，我們再次有兩種選擇。我們取 max（ Weight [2] + Table [0] [4-Weight [2]] ， Table [0] [4] ）= max（ 重量[2] +表[0] [1] ，表[0] [4] ）= MAX（ 4 + 1 ， 1 ）= 5 。

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

使用這兩個公式，我們可以填充整個 Table 陣列。我們的陣列看起來像：

+-------+--------+---+---+---+---+---+---+---+---+
| `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 |
+-------+--------+---+---+---+---+---+---+---+---+

這裡，我們在陣列中插入的最後一個值 Table [3] [7] 包含了我們所需的最大值。如果我們有 4 件物品，我們可以得到的最大值，揹包的最大容量是 7 。

這裡有一點我們必須記住，即使是第一排，重量也可能大於揹包的容量。在填充第一行時，我們需要保留另一個約束來檢查值。或者我們可以簡單地取另一行並將第一行的所有值設定為 0 。虛擬碼看起來像：

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]

這個演算法的時間複雜度是 O(n*maxCapacity)，其中 n 是專案數，maxCapacity 是我們揹包的最大容量。

到目前為止，我們已經找到了我們從示例中獲得的最大值。還有一個問題。什麼是實際物品？我們將回溯 Table 陣列中的值以找出我們採用的專案。我們將遵循兩個策略：

• 對於任何專案，如果值來自上面的位置，我們沒有采取當前專案。我們走了一步。
• 如果價值不是來自上面的位置，我們就拿走了這個專案。所以我們走上一步，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

由此我們可以說，我們可以採取第 2 項和第 3 項來獲得最大值。