【蓝桥杯】01背包 完全背包 多重背包 模板及优化

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])

优化：二进制拆分

N, V = map(int, input().split())
wv = [(0,0)] # (体积，价格)
for i in range(1, N+1):
  wi, ci, si = map(int, input().split())
  k = 1
  while si >= k:
    wv.append((k*wi, k*ci))
    si -= k
    k *= 2
  if 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 = 1
  while si >= k:
    wv.append((k*wi, k*ci))
    si -= k
    k *= 2
  if 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])