- 结论:
- 01背包问题,状态转移方程:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i])
- 完全背包问题,状态转移方程:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i]
- 空间优化后,01背包空间由小到大枚举,完全背包由大到小枚举
- 区别
- 01背包问题
- 集合:只用前i个物品,所有体积不超过总体积的方案的集合
- 属性:价值最大的方案
- 划分依据,第i个物品取不取
- 完全背包问题
- 集合:只用前i个物品,所有体积不超过总体积的方案的集合
- 属性:价值最大的方案
- 划分依据:第i个物品取几个
- 推导
- $dp[i][j] = max(dp[i-1][j], dp[i-1]j-v]+w, d[i-1][j-2v]+2w)+…$, 表示第i个物品取不同数量时的情况,每个式子对应第i个物品取0~k个同时前i-1物品随便
- 将式中的j替换为j-v,有$dp[i][j-v] = max(dp[i-1][j-v], dp[i-1]j-2v]+w, d[i-1][j-3v]+2w)+…$
- 上式左右同加w,为$dp[i][j-v]+w = max(dp[i-1][j-v]+w, dp[i-1]j-2v]+2w, d[i-1][j-3v]+3w)+…$
- 带入式一,有$dp[i][j] = max(dp[i-1][j], dp[i][j-v]+w$
# 01背包问题
line = list(map(int, input().split()))
N, V = line[0], line[1]
v, w = [], []
for _ in range(N):
line = list(map(int, input().split()))
v.append(line[0])
w.append(line[1])
dp = [[0]*(V+1) for _ in range(N+1)]
for i in range(1, N+1):
for j in range(1, V+1):
dp[i][j] = dp[i-1][j]
if j >= v[i-1]:
dp[i][j] = max(dp[i][j], dp[i-1][j-v[i-1]]+w[i-1])
print(dp[-1][-1])
# 完全背包问题
line = list(map(int, input().split()))
N, V = line[0], line[1]
v, w = [], []
for _ in range(N):
line = list(map(int, input().split()))
v.append(line[0])
w.append(line[1])
dp = [[0]*(V+1) for _ in range(N+1)]
for i in range(1, N+1):
for j in range(1, V+1):
dp[i][j] = dp[i-1][j]
if j >= v[i-1]:
dp[i][j] = max(dp[i][j], dp[i][j-v[i-1]]+w[i-1])
print(dp[-1][-1])
# 优化后的01背包问题
line = list(map(int, input().split()))
N, V = line[0], line[1]
v, w = [], []
for _ in range(N):
line = list(map(int, input().split()))
v.append(line[0])
w.append(line[1])
dp = [0 for _ in range(V+1)]
for i in range(1, N+1):
j = V
while j >= v[i-1]:
dp[j] = max(dp[j], dp[j-v[i-1]]+w[i-1])
j -= 1
print(dp[-1])
# 优化后的完全背包问题
line = list(map(int, input().split()))
N, V = line[0], line[1]
v, w = [], []
for _ in range(N):
line = list(map(int, input().split()))
v.append(line[0])
w.append(line[1])
dp = [0 for _ in range(V+1)]
for i in range(1, N+1):
j = v[i-1]
while j < V + 1:
dp[j] = max(dp[j], dp[j-v[i-1]]+w[i-1])
j += 1
print(dp[-1])