我01背包的DP解决方案有什么问题？

Question

问题是经典的0-1背包问题：

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)

您正在创建一个列表列表，但没有为每一行创建唯一的内部列表-所有行都指向同一个列表（由[（m+1）*[0]]创建的列表）。你知道吗

要修复它，请将该行更改为以下内容：

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

有关此问题的更详细描述：Nested List Indices