目錄
概念
步驟
數組轉化
周遊順序
代碼編寫
概念
W：背包最大總重量
Y：目前最大總重量限制（周遊時會變動：0~W）
N：物品的總數量
w_j：物品 j 的重量（j=0~N）
p_j：物品 j 的價值
A(j, Y)：總重量不超過Y的前提下，前 j 個物品的最高價值
步驟
| 單重+單價\總重Y | 1 | 5 | 9 |
|---|---|---|---|
| 0，0 | |||
| 1，2 | |||
| 4，3 | |||
| 5，4 |
對于j=0，A(0, Y) = 0；
對于Y=0，A(Y,0) = 0。
| 單重+單價\總重Y | 1 | 5 | 9 |
|---|---|---|---|
| 0，0 | |||
| 2，2 | |||
| 4，3 | |||
| 5，4 |
對于j=1，wj=2，pj=2，Y=1時，有wj > Y，是以放不下，是以沿用前(j-1)個時的價值，而Y不變。
| 單重+單價\總重Y | 1 | 5 | 9 |
|---|---|---|---|
| 0，0 | |||
| 2，2 | |||
| 4，3 | |||
| 5，4 |
有可能放入後的總價值，還不如不放入的高。
比如：總重量5，已經放入了(4,5)，現在要放進去(2,1)，擠出去(2,2)，那總重量更新為(4,4)，總價值變得更小了。
0560,00002,302,32,204,52,104,4??
對于j=1，wj=2，pj=2，Y=5時，有wj < Y，是以可以放下。
A(j-1，Y）：不放入目前物品時的最大價值。
A(j-1，Y-wj）：對于前j-1個物品，最大值重量為Y-wj時，看它能存的最大總價值是多少。
pj+A(j-1，Y-wj）：即先看去掉目前物品重量後，能存的最大價值，再加上目前物品的價值。
| 單重+單價\總重Y | 1 | 5 | 9 |
|---|---|---|---|
| 0，0 | |||
| 2，2 | 2,2 | 2,2 | |
| 4，3 | 4,3 | 6,5 | |
| 5，4 | 5,4 | 9,7 |
數組轉化
前 i 個物品，在最大重量限制為 j 的情況下，最大價值為 dp[i][j]。
- 由于存在0行和0列，是以長度需要額外+1。
- 重量長度 = 背包總重+1。
- 物品長度 = 物品總數+1。
- 根據遞推公式，目前 dp[i][j] 由上方或左上角的内容，推算而來。
- 最後結果隻需要傳回dp右下角的值即可。
周遊順序
兩層for循環：
- 第一層(外層)：周遊物品
- 第二層(内層)：周遊背包
- 備注：對于目前的二維數組，順序可颠倒。
for i in range(1, N+1):
for j in range(1, W+1):
... ... 複制
代碼編寫
class Solution:
def package(self, N, W, weights, values):
# 建立數組并初始化
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
# 周遊物品
for i in range(1, N+1):
# 目前物品重量
pi = values[i-1]
# 目前物品價值
wi = weights[i-1]
# 周遊背包
for j in range(1, W+1):
# 放不下的情況
if wi > j:
# 沿用前面的價值
dp[i][j] = dp[i-1][j]
# 放得下的情況
else:
# 取"放"和"不放"兩者的較大值
dp[i][j] = max(dp[i-1][j], pi+dp[i-1][j-wi])
for i in dp: print(i)
# 輸出結果
print(dp[-1][-1]) 複制
[0, 0, 0, 0, 0]
[0, 0, 4, 4, 4]
[0, 2, 4, 6, 6]
[0, 2, 4, 6, 6]
6 複制