What's wrong with my DP solution for 0-1 Knapsack?

Question

The question is classical 0-1 knapsack problem:

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. 

I wrote two solution for it, and the first recursion one works, but DP one doesn't.

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!

Can anyone help point that what's wrong with my DP solution?

Answer 1

This line is the problem:

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

You're creating a list of lists, but you're not creating a unique inner list for each row - all of the rows are pointing to the same list (the one created by [(m + 1) * [0]].

To fix it, change that line to something like this:

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

For a more detailed description of this issue: Nested List Indices