0/1 背包問題動態規劃解法

  0/1 背包問題 動態規劃解法。下面是對程式的逐步解釋及執行追踪。

def knapsack(weights,values,capacity):

    n = len(weights)

    dp = [[0]*(capacity+1) for _ in range(n+1)]

    

    for i in range(1,n+1):

        for w in range(capacity+1):

            if weights[i-1]<=w:

                dp[i][w]=max(dp[i-1][w],dp[i-1][w-weights[i-1]]+values[i-1])

            else:

                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

weights = [1,2,3,4,5]

values = [6,10,7,11,14]

capacity = 12

print(knapsack(weights, values, capacity))

# 執行結果

# 41

程式結構與邏輯

1. 初始化

   • n = len(weights): 計算物品的數量。
   • dp = [[0] * (capacity + 1) for _ in range(n + 1)]: 創建一個二維列表 dp，其中 dp[i][w] 表示當考慮前 i 個物品，背包容量為 w 時的最大價值。每個元素都初始化為 0。

2. 動態規劃狀態轉移

   • 使用兩層迴圈：
     • 外層迴圈 for i in range(1, n + 1): 用來遍歷每個物品。
     • 內層迴圈 for w in range(capacity + 1): 用來遍歷每個背包容量（從 0 到 capacity）。
   • 狀態轉移方程：
     • 如果第 i 個物品的重量小於等於當前背包容量 w，則有兩種選擇：
       1. 不放入 第 i 個物品：dp[i][w] = dp[i-1][w]
       2. 放入 第 i 個物品：dp[i][w] = dp[i-1][w - weights[i-1]] + values[i-1]
     • 取這兩者的最大值：dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
     • 如果第 i 個物品的重量超過當前背包容量 w，只能選擇不放入：dp[i][w] = dp[i-1][w]

3. 結果

   • 返回 dp[n][capacity]，這代表當考慮所有物品，且背包容量為 capacity 時，能獲得的最大價值。

追踪程式執行

以下是使用 weights = [1, 2, 3, 4, 5]，values = [6, 10, 7, 11, 14]，capacity = 12 時的 dp 表填充過程。

物品編號 (i)	重量 (weights)	價值 (values)
1	1	6
2	2	10
3	3	7
4	4	11
5	5	14

初始化 dp 表

dp 為一個 6 x 13 的二維列表，全都初始化為 0。

填表過程

1. 考慮第 1 個物品 (重量=1, 價值=6)

   • 當 w >= 1 時，可以選擇放入，因此 dp[1][w] = 6。
   • 填充結果：dp[1] = [0, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]

2. 考慮第 2 個物品 (重量=2, 價值=10)

   • 當 w < 2 時，無法放入，dp[2][w] = dp[1][w]。
   • 當 w >= 2 時，有兩種選擇：
     • 不放入：dp[2][w] = dp[1][w]
     • 放入：dp[2][w] = dp[1][w-2] + 10
   • 填充結果：dp[2] = [0, 6, 10, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16]

3. 考慮第 3 個物品 (重量=3, 價值=7)

   • 當 w < 3 時，無法放入，dp[3][w] = dp[2][w]。
   • 當 w >= 3 時，有兩種選擇：
     • 不放入：dp[3][w] = dp[2][w]
     • 放入：dp[3][w] = dp[2][w-3] + 7
   • 填充結果：dp[3] = [0, 6, 10, 16, 17, 23, 23, 23, 23, 23, 23, 23, 23]

4. 考慮第 4 個物品 (重量=4, 價值=11)

   • 當 w < 4 時，無法放入，dp[4][w] = dp[3][w]。
   • 當 w >= 4 時，有兩種選擇：
     • 不放入：dp[4][w] = dp[3][w]
     • 放入：dp[4][w] = dp[3][w-4] + 11
   • 填充結果：dp[4] = [0, 6, 10, 16, 17, 23, 23, 27, 27, 33, 33, 33, 33]

5. 考慮第 5 個物品 (重量=5, 價值=14)

   • 當 w < 5 時，無法放入，dp[5][w] = dp[4][w]。
   • 當 w >= 5 時，有兩種選擇：
     • 不放入：dp[5][w] = dp[4][w]
     • 放入：dp[5][w] = dp[4][w-5] + 14
   • 填充結果：dp[5] = [0, 6, 10, 16, 17, 23, 24, 27, 30, 33, 34, 37, 41]

最終結果

dp[5][12] = 41，表示在考慮所有 5 個物品，且背包容量為 12 時，能得到的最大價值是 41。

總結

這段程式使用了動態規劃的二維表來記錄不同狀況下的最佳解，每一步都基於前一步的計算結果，保證了時間複雜度為 ( O(n \cdot capacity) )，非常適合解決這類 0/1 背包問題。