python - 背包算法动态编程。(错误的输出)这是我到目前为止的内容

我为背包问题的动态编程实现编写了这段代码。

#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]

我得到了这个算法的错误输出我哪里做错了？

最佳答案

f = [i for i in range(n+1)]
m = [f for i in range(B+1)]

这将对每个位置使用相同的数组f，因此，例如，如果更改m，也将对每个m[1][k]更改m[i][k]你可能是故意的

m = [[i for i in range(n+1)] for i in range(B+1)]

我认为可能还有其他一些bug，所以也许您应该在某些点上打印出中间数组，以检查结果与预期不符的地方。
更新：
你的初始化对我来说很奇怪。我认为应该是i因为你需要一个零矩阵。
应该m = [[0]*n for i in range(B+1)]
您不应返回for w in range(B+1)，而应返回m[B][n]。
我的尝试，完全避免了矩阵，只使用了一个数组：

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)

关于python - 背包算法动态编程。(错误的输出)这是我到目前为止的内容，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22598225/