AcWing 5. python solution
原题链接
中等
作者:
sjytker
,
2019-08-29 11:39:39
,
所有人可见
,
阅读 2149
import collections
if __name__ == '__main__':
good = collections.namedtuple('good', ['v', 'w'])
N, V = map(int, input().split())
Goods = []
dp = [0] * (V + 1)
for i in range(N):
v, w, s = map(int, input().split())
k = 1
while k <= s:
s -= k
Goods.append(goods._make([v*k, w*k]))
k *= 2
if s > 0: Goods.append(goods._make([v*s, w*s]))
for good in Goods:
for j in range(V, good.v - 1, -1):
dp[j] = max(dp[j], dp[j - good.v] + good.w)
print(dp[V])
为什么我用楼主的提交进去是错误的,就算把goods改为good也是错误的,我自己写了一段类似的代码,报错跟楼主一致。n, V = map(int, input().split())
goods = []
dp = [0] * (V + 1)
for _ in range(n):
v, w, s = map(int, input().split())
goods.append((v, w, s))
def binary_optimization(n, V, goods):
N = []
for v, w, s in goods:
k = 1
while k <= s:
vs = v * k
ws = w * k
N.append((vs, ws))
s -= k
k *= 2
N_result = binary_optimization(n, V, goods)
for i in range(len(N_result)):
for j in range(V, N_result[i][0] - 1, -1):
dp[j] = max(dp[j], dp[j - N_result[i][0]] + N_result[i][1])
print(dp[V])
while k <= s: 把=去掉,那么if s > 0的判断也可以去掉了
很nice
不错不错第一次见
二进制转换很厉害,楼主有笔误,那个goods应该是good。楼主用了nametyple,显得更高端
感觉精通或熟练使用collections内各种功能如
namedtuple
对效率提升很明显啊不用namedtuple,直接用元组存(v乘k,w乘k)是可以的,而且运行速度更快