2024年10月24日 星期四

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)
116
2210
337
4411
5514

初始化 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 背包問題

沒有留言:

張貼留言