python - 背包算法动态规划。(不正确的输出)这是我到目前为止所拥有的

Question

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

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

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

Answer 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)