AcWing 2. 01背包问题 - Python3
原题链接
简单
作者:
不觉间已被迷惑
,
2020-02-26 17:21:16
,
所有人可见
,
阅读 1612
# f[i][j]表示只看前i件物品,在容积是j的情况下,可以装的总价值是多大
# result = max{f[n][0~v]
# 递推公式
# 1.不选第i个物品 f[i][j] = f[i-1][j]
# 2.选第i个物品 f[i][j] = f[i-1][j-v[i]] + w[i]
# 初始化
# f[0][0] = 0;
N, V = map(int, input().split())
# 在这里给两个list赋了初值0,这是让他们的索引和所处位置对应上,不然后面可能会找错位置
vlist, wlist = [0], [0]
for i in range(N):
tmp = list(map(int, input().split()))
vlist.append(tmp[0])
wlist.append(tmp[1])
##### 二维递归方法
# 创建二维表
f = [[0 for _ in range(V+1)] for _ in range(N+1)]
for i in range(1, N+1):
for j in range(1, V+1):
# 如果第i个物品的体积比上限容积要大,则不拿该物品
if vlist[i] > j:
f[i][j] = f[i-1][j]
# 如果不比上限容积大,那么是否拿之,取决于拿或不拿哪种的价值更高
else:
f[i][j] = max(f[i-1][j], f[i-1][j-vlist[i]]+wlist[i])
print(f[-1][-1])
##### 一维递归方法(优化空间复杂度)
# 创建一维表
f = [0 for _ in range(V+1)]
for i in range(1, N+1):
for j in range(V, 0, -1):
if vlist[i] <= j:
f[j] = max(f[j], f[j-vlist[i]]+wlist[i])
print(f[-1])
请问为什么运行出来会报错,还需要加别的代码吗?
您好,我想请问下为什么第一行就报错