01背包
N, V = map(int, input().split())
w = [0] * (N+1) # 体积
c = [0] * (N+1) # 价格dp = [[0] * (V+1) for i in range(N+1)] # dp[i][j] 前i个物品空间j下最大价值
for i in range(1, N+1):w[i], c[i] = map(int, input().split())for i in range(1, N+1):for j in range(1, V+1):if w[i] > j: dp[i][j] = dp[i-1][j]else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i])
print(dp[-1][-1])
滚动数组优化
N, V = map(int, input().split())
w = [0] * (N+1) # 体积
c = [0] * (N+1) # 价格dp = [0] * (V+1) # dp[i][j] 前i个物品空间j下最大价值
for i in range(1, N+1):w[i], c[i] = map(int, input().split())for i in range(1, N+1):for j in range(V, w[i]-1, -1):dp[j] = max(dp[j], dp[j-w[i]] + c[i])
print(dp[-1])
完全背包
dp推导
最朴素的写法：
for i in range(1, N+1):for j in range(1, V+1):if w[i] > j: dp[i][j] = dp[i-1][j]else: for k in range(1, j // w[i] + 1):dp[i][j] = max(dp[i-1][j], dp[i-1][j-k*w[i]] + k*c[i])
优化
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i], dp[i-1][j-2*w[i]] + 2*c[i], ..., dp[i-1][j-k*w[i]] + k*c[i]) # 1 + j//w[i]
考虑
dp[i][j-w[i]] = max(dp[i-1][j-w[i]], dp[i-1][j-2*w[i]] + c[i], dp[i-1][j-3*w[i]] + 2*c[i], ..., dp[i-1][j-k*w[i]] + (k-1)*c[i]) # 1 + j//w[i]
可得
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + c[i])
N, V = map(int, input().split())
w = [0] * (N+1) # 体积
c = [0] * (N+1) # 价格dp = [[0] * (V+1) for i in range(N+1)] # dp[i][j] 前i个物品空间j下最大价值
for i in range(1, N+1):w[i], c[i] = map(int, input().split())for i in range(1, N+1):for j in range(1, V+1):if w[i] > j: dp[i][j] = dp[i-1][j]else: dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + c[i])
print(dp[-1][-1])
滚动数组优化
N, V = map(int, input().split())
w = [0] * (N+1) # 体积
c = [0] * (N+1) # 价格dp = [0] * (V+1) # dp[i][j] 前i个物品空间j下最大价值
for i in range(1, N+1):w[i], c[i] = map(int, input().split())for i in range(1, N+1):for j in range(w[i], V+1):dp[j] = max(dp[j], dp[j-w[i]] + c[i])
print(dp[-1])
多重背包
朴素思维：拆分当成01背包
N, V = map(int, input().split())
w = [0] # 体积
c = [0] # 价格for i in range(1, N+1):wi, ci, si = map(int, input().split())w = w + [wi for i in range(si)]c = c + [ci for i in range(si)] n = len(w) - 1
dp = [[0] * (V+1) for i in range(n+1)]
for i in range(1, n+1):for j in range(1, V+1):if w[i] > j: dp[i][j] = dp[i-1][j]else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i])
print(dp[-1][-1])
优化：二进制拆分
| nums | w | c |
|---|---|---|
| 1 | w | 2c |
| 2 | 2w | 3c |
| 4 | 4w | 4c |
| … | … | … |
| res | res*w | res*c |
N, V = map(int, input().split())
wv = [(0,0)] # (体积，价格)
for i in range(1, N+1):wi, ci, si = map(int, input().split())k = 1while si >= k:wv.append((k*wi, k*ci))si -= kk *= 2if si!=0:wv.append((si*wi, si*ci))n = len(wv)-1
dp = [[0] * (V+1) for i in range(n+1)] for i in range(1, n+1):wi, ci = wv[i]for j in range(1, V+1):if wi > j: dp[i][j] = dp[i-1][j]else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + ci)
print(dp[-1][-1])
二进制拆分 + 滚动数组优化
N, V = map(int, input().split())
wv = [(0,0)] # (体积，价格)
for i in range(1, N+1):wi, ci, si = map(int, input().split())k = 1while si >= k:wv.append((k*wi, k*ci))si -= kk *= 2if si!=0:wv.append((si*wi, si*ci))n = len(wv)-1
dp = [0] * (V+1) for i in range(1, n+1):wi, ci = wv[i]for j in range(V, wi-1 , -1):dp[j] = max(dp[j], dp[j-wi] + ci)
print(dp[-1])