AcWing 3. 完全背包问题(python3代码)
原题链接
简单
作者:
PandaWaKaKa
,
2019-08-25 14:23:09
,
所有人可见
,
阅读 2114
一维动态规划
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 = j//goods[i][0]
dp[j] = max([dp[j- x* goods[i][0]] + x * goods[i][1] for x in range(k+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): # 从前往后
if j >= goods[i][0]:
dp[j] = max(dp[j], dp[j-goods[i][0]]+goods[i][1])
print(dp[-1])
哥们你这个是错的啊,完全背包的j循环不用逆序
你提供的第一种方案,时间复杂度太高了,会报错
Traceback (most recent call last):
File “a.py”, line 1, in [HTML_REMOVED]
n, v = map(int, input().split())
File “[HTML_REMOVED]“, line 1
4 5
^
SyntaxError: invalid syntax
我把你的代码复制过去 报错是是怎么回事
niuwa niuwa
太牛了哥
优化代码的二层循环中可以从goods[i][0]做起始点,这样就不用if判断了,而且节省循环次数。