我的DP解決方案0-1 Knapsack有什麼問題？

Question

問題是經典的揹包問題：

Given n items with size A[i], an integer m denotes the size of a backpack. How full you can fill this backpack? 

Example 
If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select 2, 3 and 5, so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack. 

我寫了兩個解決方案，這和第一個遞歸一件作品，但DP一個沒有。

class Solution: 
    # @param m: An integer m denotes the size of a backpack 
    # @param A: Given n items with size A[i] 
    # @return: The maximum size 
    def backPack(self, m, A): 
     if len(A) <= 0 or m <= 0: 
      return 0 
     if A[0] > m: 
      return self.backPack(m, A[1:]) 
     put = A[0] + self.backPack(m - A[0], A[1:]) 
     not_put = self.backPack(m, A[1:]) 
     return max(put, not_put) 

    def YetAnotherBackPack(self, m, A): 
     mapping = [(m + 1) * [0]] * (len(A) + 1) 
     for i in range(len(A) + 1): 
      for j in range(m + 1): 
       if i == 0 or j == 0: 
        mapping[i][j] = 0 
       elif A[i - 1] > j: 
        mapping[i][j] = mapping[i - 1][j] 
       else: 
        put = mapping[i - 1][j - A[i - 1]] + A[i - 1] 
        mapping[i][j] = max(mapping[i - 1][j], put) 

     return mapping[len(A)][m] 

print Solution().backPack(10, [3, 4, 8, 5]) # output: 9 
print Solution().YetAnotherBackPack(10, [3, 4, 8, 5]) # output: 10 WRONG! 

任何人都可以幫忙指出，我的DP解決方案有什麼問題嗎？

Answer 1

這條線的問題是：

mapping = [(m + 1) * [0]] * (len(A) + 1) 

你正在創建一個列表的列表，但你沒有創建於各行的唯一內部列表 - 所有行的都指向同一個列表。

mapping = [[0 for i in range(m+1)] for j in range(len(A) + 1)] 

對於這一問題的更詳細的描述：Nested List Indices（由[（M + 1）* [0]]

爲了修正它，該行更改爲像這樣產生的一個