AcWing 4. 多重背包问题 I(python3代码)
原题链接
简单
作者:
PandaWaKaKa
,
2019-08-25 16:53:43
,
所有人可见
,
阅读 1565
转换为01背包
n,v = map(int, input().split())
goods = []
for i in range(n):
goods.append([int(i) for i in input().split()])
new_goods = []
for i in range(n):
for j in range(goods[i][2]):
new_goods.append(goods[i][0:2])
goods = new_goods
n = len(goods)
dp = [0 for i in range(v+1)]
for i in range(n):
for j in range(v,-1,-1):
if j>= goods[i][0]:
dp[j] = max(dp[j], dp[j - goods[i][0]] + goods[i][1])
print(dp[-1])
一维动态规划
n,v = map(int, input().split())
goods = []
for i in range(n):
goods.append([int(i) for i in input().split()])
dp = [0 for i in range(v+1)]
for i in range(n):
for j in range(v, -1, -1):
# 考虑两种情况的最小值
k = min(j//goods[i][0], goods[i][2])
dp[j] = max([dp[j-x*goods[i][0]] + x*goods[i][1] for x in range(k+1)])
print(dp[-1])