前言: 總結(jié)模板
0X00 模板總結(jié)
首先背包問題對于「狀態(tài)」有一個(gè)通用的表示方法: dp[i][j]
代表使用前 i 個(gè)物體在不超過體積 j 的情況下的獲得的最大價(jià)值
理所應(yīng)當(dāng)可以根據(jù)第 i 個(gè)物品計(jì)算狀態(tài)
0 1 背包問題
根據(jù)第 i 個(gè)物品使不使用可以寫出「狀態(tài)轉(zhuǎn)移方程」:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v]+w)
意思就是使用該物品和不使用該物品取一個(gè)最大值
寫出 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])
優(yōu)化成 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 背包問題上加上了物品個(gè)數(shù)不限, 劃分從選不選變成了選幾個(gè)
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])
優(yōu)化成 :
已知:
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])
優(yōu)化成一維 dp:
直接去掉一維, 由于是從當(dāng)前層來的, 所以順序是從小到大
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 背包問題上加上了物品個(gè)數(shù)有限, 劃分從選不選變成了選幾個(gè)
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])
優(yōu)化從 到
其中:
- s 是最多物品個(gè)數(shù)
基本原理如下:
0 ~ 200
可以被
1, 2, 4, 8, 16, 32, 64, 73
表示
所以任意一個(gè)物品的個(gè)數(shù)可以拆分, 比如有個(gè)物品的個(gè)數(shù)是 200 就可以由 代表著 1, 2, 4, 8, 16, 32, 64, 73 的 8 個(gè)新物品表示
最后使用 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 背包解決這個(gè)問題
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])
分組背包問題
分組背包問題的狀態(tài)表示方程的含義就有點(diǎn)變化了
dp[i][j] 表示使用 前 i 組物品, 在不超過 j 體積的情況下的最大價(jià)值
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])
