前言: 总结模板
0X00 模板总结
首先背包问题对于「状态」有一个通用的表示方法: dp[i][j]
代表使用前 i 个物体在不超过体积 j 的情况下的获得的最大价值
理所应当可以根据第 i 个物品计算状态
0 1 背包问题
根据第 i 个物品使不使用可以写出「状态转移方程」:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v]+w)
意思就是使用该物品和不使用该物品取一个最大值
写出 0 1 背包的通用解法:
n, cap = map(int, input().split())
mat = [[0] * 2 for _ in range(n+1)]
for x in range(1, n+1):
mat[x][:] = map(int, input().split())
dp = [[0] * (cap + 1) for _ in range(n+1)]
for x in range(1, n+1):
v, w = mat[x]
for y in range(cap+1):
dp[x][y] = dp[x-1][y]
if y < v: continue
dp[x][y] = max(dp[x][y], dp[x-1][y-v]+w)
print(dp[n][cap])
优化成 1 维 dp
n, cap = map(int, input().split())
mat = [[0] * 2 for _ in range(n+1)]
for x in range(1, n+1):
mat[x][:] = map(int, input().split())
dp = [0] * (cap + 1)
for x in range(1, n+1):
v, w = mat[x]
for y in range(cap, v-1, -1):
dp[y] = max(dp[y], dp[y-v]+w)
print(dp[cap])
完全背包问题
「完全背包」问题就是在 01 背包问题上加上了物品个数不限, 划分从选不选变成了选几个
n, cap = map(int, input().split())
mat = [[0] * 2 for i in range(n+1)]
for x in range(1, n+1):
mat[x][:] = map(int, input().split())
dp = [[0] * (cap+1) for _ in range(n+1)]
for x in range(1, n+1):
for y in range(cap+1):
k, v, w = 0, mat[x][0], mat[x][1]
while k * v <= y:
dp[x][y] = max(dp[x][y], dp[x-1][y - k*v] + k*w)
k += 1
print(dp[n][cap])
优化成 :
已知:
dp[x][y] = max(dp[x-1][y], dp[x-1][y-v] + w, dp[x-1][y-2*v]+2*w+...+dp[x-1][y-k*v]+k*w) y > k*v
dp[x][y-v] = max(dp[x-1][y-v], dp[x-1][y-2*v] + w, ..., dp[x-1][y-k*v]+k*w) y > k*v
所以
dp[x][y] = max(dp[x-1][y], dp[x][y-v]+w)
n, cap = map(int, input().split())
mat = [[0] * 2 for i in range(n+1)]
for x in range(1, n+1):
mat[x][:] = map(int, input().split())
dp = [[0] * (cap+1) for _ in range(n+1)]
for x in range(1, n+1):
v, w = mat[x][0], mat[x][1]
for y in range(cap+1):
dp[x][y] = dp[x-1][y]
if y < v: continue
dp[x][y] = max(dp[x][y], dp[x][y - v] + w)
print(dp[n][cap])
优化成一维 dp:
直接去掉一维, 由于是从当前层来的, 所以顺序是从小到大
n, cap = map(int, input().split())
mat = [[0] * 2 for i in range(n+1)]
for x in range(1, n+1):
mat[x][:] = map(int, input().split())
dp = [0] * (cap+1)
for x in range(1, n+1):
v, w = mat[x][0], mat[x][1]
for y in range(v, cap+1):
dp[y] = max(dp[y], dp[y - v] + w)
print(dp[cap])
多重背包问题
「多重背包」问题就是在 01 背包问题上加上了物品个数有限, 划分从选不选变成了选几个
n, cap = map(int, input().split())
mat = [[0] * 3 for _ in range(n+1)]
for x in range(1, n+1):
mat[x][:] = map(int, input().split())
dp = [[0] * (cap+1) for _ in range(n+1)]
for x in range(1, n+1):
for y in range(cap+1):
v, w, num = mat[x]
for k in range(num+1):
if k * v > y: break
dp[x][y] = max(dp[x][y], dp[x-1][y - k*v]+k*w)
print(dp[n][cap])
优化从 到
其中:
- s 是最多物品个数
基本原理如下:
0 ~ 200
可以被
1, 2, 4, 8, 16, 32, 64, 73
表示
所以任意一个物品的个数可以拆分, 比如有个物品的个数是 200 就可以由 代表着 1, 2, 4, 8, 16, 32, 64, 73 的 8 个新物品表示
最后使用 01 背包解决
n, cap = map(int, input().split())
mat = [[0, 0] for _ in range(15000)]
cnt = 1
for _ in range(1, n+1):
v, w, s = map(int, input().split())
k = 1
while k <= s:
mat[cnt][0], mat[cnt][1] = k*v, k*w
cnt += 1
s -= k
k *= 2
if s > 0:
mat[cnt][0], mat[cnt][1] = s*v, s*w
cnt += 1
# 01 背包解决这个问题
n = cnt - 1
dp = [0] * (cap+1)
for x in range(n+1):
v, w = mat[x]
for y in range(cap, v-1, -1):
dp[y] = max(dp[y], dp[y-v] + w)
print(dp[cap])
分组背包问题
分组背包问题的状态表示方程的含义就有点变化了
dp[i][j] 表示使用 前 i 组物品, 在不超过 j 体积的情况下的最大价值
n, cap = map(int, input().split())
mat = [[]for _ in range(n+1)]
for x in range(1, n+1):
m = int(input())
for y in range(m):
temp = list(map(int, input().split()))
mat[x].append(temp)
dp = [[0] * (cap+1) for _ in range(n+1)]
for x in range(1, n+1):
for y in range(cap+1):
# 不使用 x 组
dp[x][y] = dp[x-1][y]
# 使用 x 组
for k in range(len(mat[x])):
v, w = mat[x][k]
# 使用 1 次
if y < v: continue
dp[x][y] = max(dp[x][y], dp[x-1][y - v] + w)
print(dp[n][cap])
