AcWing 9. 分组背包问题(python3)
原题链接
中等
作者:
小小呆
,
2019-09-14 21:28:37
,
所有人可见
,
阅读 1233
def group_pack(n,v,goods):
dp = [0]*(v+1)
for group in goods:
#注意枚举的顺序
#先进行体积的枚举,再进行每种商品决策的枚举
#对于n种商品,一共有n+1种决策
for j in range(v, -1, -1):
for cost,value in group:
if j >= cost:
dp[j] = max(dp[j],dp[j-cost] + value)
return dp[v]
if __name__ == '__main__':
n,v = map(int,input().split())
goods = []
for i in range(n):
group_num = int(input())
group = [list(map(int,input().split()))for j in range(group_num)]
goods.append(group)
print(group_pack(n,v,goods))