Python3_分组背包问题
作者:
成理第一深情
,
2024-02-06 10:33:40
,
所有人可见
,
阅读 46
"""
状态表示:
集合:f[i][j]:只选前i组物品,并且体积不超过j
属性:最大价值
状态计算:
选第i组物品中的哪一个
f[i][j] = max(f[i - 1][j - v[i][1]] + w[i][1]... , f[i - 1][j - v[i][s]] + w[i][s])
对于每个状态都是从上一层状态中转移过来,因此如果优化到一维需要从大到小枚举
我初学者先写二维,后面理解深刻之后再写一维
"""
n, m = map(int, input().strip().split())
N = 110
v = [[0] * 110 for _ in range(N)]
w = [[0] * 110 for _ in range(N)]
s = [0 for _ in range(N)]
for i in range(1, n + 1):
s[i] = int(input())
for j in range(1, s[i] + 1):
a, b = map(int, input().strip().split())
v[i][j] = a
w[i][j] = b
f = [[0] * N for _ in range(N)]
for i in range(1, n + 1):
for j in range(1, m + 1):
# 不选第i组物品
f[i][j] = f[i - 1][j] # 出错,这个要放在下一个循环之前,否则一直被更新
for k in range(1, s[i] + 1):
# 选第i组物品中的哪一个
if j >= v[i][k]:
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k])
print(f[n][m])