DSA 0/1 揹包問題

0/1 揹包問題

0/1 揹包問題是指您有一個有重量限制的揹包，並且您身處一個裝滿寶藏的房間，每個寶藏都有其價值和重量。

要解決 0/1 揹包問題，您必須找出要裝哪些寶藏才能使總價值最大化，同時保持低於揹包的重量限制。

太棒了！您找到了能帶來最大價值的物品😀

1

2

3

揹包

$ {{ totalValue }}

{{ totalWeight }}/{{limit}} 公斤

{{ item.name }}

$ {{ item.value }}

{{ item.weight }} 公斤

您能手動解決上面的 0/1 揹包問題嗎？繼續閱讀以瞭解解決 0/1 揹包問題的不同實現方式。

解決 0/1 揹包問題有助於企業在預算內決定資助哪些專案，從而在不超支的情況下實現利潤最大化。它還用於物流中，以最佳化貨物裝載到卡車和飛機上，確保在不超過重量限制的情況下包含最有價值或優先順序最高的物品。

暴力破解法

使用暴力破解法意味著檢查所有可能性，尋找最佳結果。這通常是解決問題最直接的方法，但也需要最多的計算。

使用暴力破解法解決 0/1 揹包問題意味著：

1. 計算揹包中每種可能物品組合的價值。
2. 丟棄超過揹包重量限制的組合。
3. 選擇總價值最高的物品組合。

這種解決 0/1 揹包問題的暴力破解法可以這樣實現：

def knapsack_brute_force(capacity, n):
    print(f"knapsack_brute_force({capacity},{n})")
    if n == 0 or capacity == 0:
        return 0

    elif weights[n-1] > capacity:
        return knapsack_brute_force(capacity, n-1)

    else:
        include_item = values[n-1] + knapsack_brute_force(capacity-weights[n-1], n-1)
        exclude_item = knapsack_brute_force(capacity, n-1)
        return max(include_item, exclude_item)

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
n = len(values)

print("\nMaximum value in Knapsack =", knapsack_brute_force(capacity, n))

執行上述程式碼意味著 knapsack_brute_force 函式會被多次遞迴呼叫。您可以從所有列印輸出中看到這一點。

每次呼叫函式時，它都會包含當前項 n-1 或不包含。

第 2 行：此列印語句向我們顯示了函式每次被呼叫的情況。

第 3-4 行：如果物品已用完 (n==0) 或容量已用完 (capacity==0)，則不再進行遞迴呼叫，因為此時不能再向揹包中新增物品。

第 6-7 行：如果當前物品比容量重 (weights[n-1] > capacity)，則放棄當前物品並轉到下一個物品。

第 10-12 行：如果當前物品可以新增到揹包中，則檢視哪種情況能帶來最高價值：添加當前物品，或不添加當前物品。

執行程式碼示例會建立一個遞迴樹，如下所示，每個灰色框表示一次函式呼叫。

從上面的遞迴樹中可以看出，例如，如果拿走皇冠、杯子和地球儀，則顯微鏡（2公斤）就沒有空間了，這會給我們帶來 200+400+500=1100 的總價值。

我們還可以看到，只拿顯微鏡會給我們帶來 300 的總價值（右下角的灰色框）。

正如您在上面的遞迴樹中以及透過執行示例程式碼所看到的，函式有時會以相同的引數被呼叫，例如 knapsack_brute_force(2,0) 就被呼叫了兩次。我們透過使用記憶化來避免這種情況。

記憶化方法（自上而下）

記憶化技術將之前的函式呼叫結果儲存在一個數組中，這樣就可以從該陣列中獲取之前的結果，而無需再次計算。

在此處閱讀更多關於記憶化的資訊。

記憶化是一種“自上而下”的方法，因為它透過分解為越來越小的子問題來開始解決問題。

在上面的暴力破解示例中，相同的函式呼叫只發生了幾次，所以使用記憶化的效果不是很大。但在其他有更多物品可供選擇的示例中，記憶化技術將更有幫助。

在用記憶化改進了暴力破解實現之後，程式碼現在看起來像這樣：

def knapsack_memoization(capacity, n):
    print(f"knapsack_memoization({n}, {capacity})")
    if memo[n][capacity] is not None:
        print(f"Using memo for ({n}, {capacity})")
        return memo[n][capacity]
    
    if n == 0 or capacity == 0:
        result = 0
    elif weights[n-1] > capacity:
        result = knapsack_memoization(capacity, n-1)
    else:
        include_item = values[n-1] + knapsack_memoization(capacity-weights[n-1], n-1)
        exclude_item = knapsack_memoization(capacity, n-1)
        result = max(include_item, exclude_item)

    memo[n][capacity] = result
    return result

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
n = len(values)

memo = [[None]*(capacity + 1) for _ in range(n + 1)]

print("\nMaximum value in Knapsack =", knapsack_memoization(capacity, n))

上面程式碼中高亮顯示的部分展示了用於改進之前暴力破解實現的記憶化技術。

第 24 行：建立一個數組 memo 來儲存之前的結果。

第 3-5 行：在函式開始時，在進行任何計算或遞迴呼叫之前，檢查結果是否已找到並存儲在 memo 陣列中。

第 16 行：儲存結果以備後用。

列表法（自下而上）

解決 0/1 揹包問題的另一種技術是使用一種稱為列表法的方法。這種方法也稱為迭代法，是動態規劃中使用的一種技術。

列表法以自下而上的方式解決問題，首先用最基本的子問題的結果填充表格。然後使用之前的結果填充下一個表格值。

使用下面的動畫來查看錶格是如何逐格填充的，使用之前計算的值，直到得出最終結果。

列表法透過一次考慮一件物品，並逐步增加揹包容量來工作。透過這種方式，透過首先解決最基本的子問題來構建解決方案。

在每一行，都會考慮將一件物品新增到揹包中，並增加容量。

def knapsack_tabulation():
    n = len(values)
    tab = [[0]*(capacity + 1) for y in range(n + 1)]

    for i in range(1, n+1):
        for w in range(1, capacity+1):
            if weights[i-1] <= w:
                include_item = values[i-1] + tab[i-1][w-weights[i-1]]
                exclude_item = tab[i-1][w]
                tab[i][w] = max(include_item, exclude_item)
            else:
                tab[i][w] = tab[i-1][w]
    
    for row in tab:
    	  print(row)
    return tab[n][capacity]

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
print("\nMaximum value in Knapsack =", knapsack_tabulation())

第 7-10 行：如果物品重量小於容量，則表示可以新增該物品。檢查新增它是否會獲得比上一行（表示不新增該物品）計算出的結果更高的總價值。使用這兩個值中的最高值 (max)。換句話說：選擇帶走或不帶走當前物品。

第 8 行：這一行可能最難理解。要找到與添加當前物品相對應的價值，我們必須使用 values 陣列中當前物品的價值。但除此之外，我們必須用當前物品的重量減少容量，以檢視剩餘容量是否能給我們帶來任何額外價值。這類似於檢查除了當前物品之外是否可以新增其他物品，並新增這些物品的價值。

第 12 行：如果當前物品比容量重（太重），則只需填入上一行的值，這表示不添加當前物品。

手動演練

以下是關於表格中一些值如何計算的解釋列表。您可以在閱讀時點選上面動畫中相應的表格單元格以獲得更好的理解。

顯微鏡，容量 1 公斤：對於計算出的第一個值，檢查在重量限制為 1 公斤的情況下，顯微鏡是否可以放入袋中。顯微鏡重 2 公斤，太重了，所以值 0 直接從上面單元格中複製，表示揹包中沒有物品。只考慮一個重量限制為 1 公斤的袋子中的顯微鏡，意味著我們不能帶任何物品，必須空手而歸，總價值為 0 美元。

顯微鏡，容量 2 公斤：對於計算出的第二個值，我們能夠將顯微鏡放入重量限制為 2 公斤的袋子中，所以我們可以帶上它，袋子中的總價值是 300 美元（顯微鏡的價值）。對於更高的揹包容量，只考慮顯微鏡，意味著我們可以帶上它，所以該行中的所有其他值都是 300 美元。

地球儀，容量 1 公斤：考慮一個重 1 公斤的地球儀和一個容量為 1 公斤的揹包，這意味著我們可以帶走地球儀，因此價值為 200 美元。程式碼會找出帶走地球儀（價值 200 美元）與之前計算出的 1 公斤容量下的價值（0 美元，來自上方單元格）中的最大值。在這種情況下，很明顯我們應該帶走地球儀，因為它是唯一重量如此低的物品，但在其他情況下，之前在相同容量下計算出的價值可能更高。

地球儀，容量 2 公斤：在容量為 2 公斤時，程式碼發現地球儀可以裝下，這給了我們 200 美元的價值，但顯微鏡就裝不下了。而如果裝下顯微鏡（容量為 2 公斤）則會給我們帶來 300 美元的價值，這更高，所以選擇顯微鏡（來自上方單元格的價值）是最大化此表格單元格揹包價值的選擇。

地球儀，容量 3 公斤：考慮容量為 3 公斤的地球儀，意味著我們可以帶走地球儀，但剩餘的 2 公斤容量也可以帶走顯微鏡。在這個單元格中，同時帶走地球儀和顯微鏡會給我們帶來更高的價值 200+300=500，而不是隻帶走顯微鏡（如上一行計算所示），所以這兩個物品都被帶走了，單元格值為 500。

哪些物品能給我們帶來最高價值？

在填充完表格並找到揹包可以擁有的最大值後，我們不清楚需要攜帶哪些物品才能獲得該價值。

為了找到包含的物品，我們使用已建立的表格，並從右下角具有最高值的單元格開始，在我們的例子中是值為 1200 的單元格。

這是使用逐步方法找到包含的物品的圖示：

這是找到所含物品的方法

1. 右下角的值是 1200，上面的單元格是 900。值不同，這意味著包含皇冠。
2. 我們要去的下一個單元格在上面一行，我們向左移動與皇冠重量相同的次數，即向左移動 3 個位置到值為 700 的單元格。
3. 我們現在所在的單元格的值是 700，上面單元格的值是 500。值不同，這意味著當前行的物品包含在內：杯子。
4. 杯子重 5 公斤，所以我們去的下一個單元格在上面一行，向左 5 個位置，到值為 300 的單元格，在考慮地球儀的那一行。
5. 由於上方單元格的值與當前值為 300 的單元格相同，這意味著地球儀不包含在內，我們要去的下一個單元格是正上方的顯微鏡所在的 300 值的單元格。
6. 由於上面的單元格與當前值為 300 的單元格不同，這意味著顯微鏡已包含在內。
7. 我們要去的下一個單元格在上面一行，向左兩個位置，因為顯微鏡重 2 公斤。
8. 我們到達了左上角的單元格。由於值為 0，表示我們已完成。

當包含這些物品時，我們的 0/1 揹包問題具有最大價值：皇冠、杯子和顯微鏡。

相同的步驟新增到下面的程式碼中，以找到構成 0/1 揹包問題解決方案的物品。

def knapsack_tabulation():
    n = len(values)
    tab = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                include_item = values[i-1] + tab[i-1][w - weights[i-1]]
                exclude_item = tab[i-1][w]
                tab[i][w] = max(include_item, exclude_item)
            else:
                tab[i][w] = tab[i-1][w]

    for row in tab:
        print(row)

    items_included = []
    w = capacity
    for i in range(n, 0, -1):
        if tab[i][w] != tab[i-1][w]:
            items_included.append(i-1)
            w -= weights[i-1]

    print("\nItems included:", items_included)

    return tab[n][capacity]

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
print("\nMaximum value in Knapsack =", knapsack_tabulation())

時間複雜度

解決 0/1 揹包問題有三種方法，它們的執行方式和時間複雜度不同。

暴力破解法：這是三種方法中最慢的一種。可能性以遞迴方式檢查，時間複雜度為 \(O(2^n)\)，其中 \(n\) 是我們可以裝入的潛在物品數量。這意味著每增加一個需要考慮的物品，計算量就會翻倍。

記憶化方法：透過記憶之前的結果來節省計算，從而獲得更好的時間複雜度 \(O(n \cdot C)\)，其中 \(n\) 是物品數量，\(C\) 是揹包容量。此方法以與暴力破解法相同的遞迴方式執行。

列表法：時間複雜度與記憶化方法相同，為 \(O(n \cdot C)\)，其中 \(n\) 是物品數量，\(C\) 是揹包容量，但記憶體使用和執行方式更具可預測性，這通常使得列表法最受青睞。