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
程式結構與邏輯
初始化
n = len(weights)
: 計算物品的數量。dp = [[0] * (capacity + 1) for _ in range(n + 1)]
: 創建一個二維列表dp
,其中dp[i][w]
表示當考慮前i
個物品,背包容量為w
時的最大價值。每個元素都初始化為 0。
動態規劃狀態轉移
- 使用兩層迴圈:
- 外層迴圈
for i in range(1, n + 1)
: 用來遍歷每個物品。 - 內層迴圈
for w in range(capacity + 1)
: 用來遍歷每個背包容量(從 0 到capacity
)。
- 外層迴圈
- 狀態轉移方程:
- 如果第
i
個物品的重量小於等於當前背包容量w
,則有兩種選擇:- 不放入 第
i
個物品:dp[i][w] = dp[i-1][w]
- 放入 第
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]
- 如果第
- 使用兩層迴圈:
結果
- 返回
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, 價值=6)
- 當
w >= 1
時,可以選擇放入,因此dp[1][w] = 6
。 - 填充結果:
dp[1] = [0, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
- 當
考慮第 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, 價值=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, 價值=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, 價值=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 背包問題。
沒有留言:
張貼留言