python - 我的 0-1 Knapsack 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