问题描述
我为背包问题的动态编程实现编写了这段代码。
#B = maximum weight
#n = number of items
#p = list of weights
#a = list of values
#p[i] = weight with value a[i]
def maximum_attractiveness(n, B, p, a):
f = [i for i in range(n+1)]
m = [f for i in range(B+1)]
m[0] = [0 for i in range(len(m[0]))]
for i in m:
i[0] = 0
print(m)
for j in range(n):
for w in range(B):
if (p[j]) > (w):
m[w][j] = m[w][j-1]
else:
m[w][j] = max(m[w][j-1],m[w-p[j]][j-1]+a[j])
return m[B][n]
我得到的算法输出不正确。 我哪里做错了？
1楼
f = [i for i in range(n+1)]
m = [f for i in range(B+1)]
这对每个位置m使用相同的数组f ，因此例如如果你改变m[1][k] ，你也改变每个i m[i][k] 。
你可能想做
m = [[i for i in range(n+1)] for i in range(B+1)]
我认为可能还有一些其他的错误，所以也许你应该在某些点打印出中间数组，以检查结果不是你期望它们的位置。
更新：
-
你的初始化对我来说很奇怪。
我认为它应该只是
m = [[0]*n for i in range(B+1)]因为你需要一个零矩阵。 -
它应该是
for w in range(B+1) -
你不应该返回
m[B][n]，而是max(m[j][n] for j in range(B+1))。
我的尝试，它完全避免了矩阵，只使用一个数组：
m = [0]*(B+1)
for j in range(n):
for w in range(B,p[j]-1,-1):
m[w] = max(m[w], m[w-p[j]] + a[j])
return max(m)