古典背包问题的产出差异

Question

我为一个经典的背包问题写了一个程序，它运行良好。

以下是代码：

class Solution:

    def knapsack(self, wt, val, crr_cap, n):
        if crr_cap == 0 or n == 0:
            return 0

        b = self.knapsack(wt, val, crr_cap, n - 1)

        if wt[n - 1] <= crr_cap:
            a = val[n - 1] + self.knapsack(wt, val, crr_cap - wt[n - 1], n - 1)
            return max(a, b)

        else:
            return b

    def getMaximumvalue(self, weight, value, capacity) -> int:

        ret = self.knapsack(weight, value, capacity, len(weight))
        return ret


a = Solution()
weight = [1, 2, 3, 4, 5, 6]
value = [4, 5, 6, 7, 8, 9]

然后，我向其添加了remoization，基本上是通过添加4个新行。

以下是更新的代码：

class Solution:
    def __init__(self):
        self.dp = None

    def knapsack(self, wt, val, crr_cap, n):
        if crr_cap == 0 or n == 0:
            return 0

        """
        Below is the new added condition
        Checking if the value is present in the cache
        """
        if self.dp[n][crr_cap] != -1:
            return self.dp[n][crr_cap]

        b = self.knapsack(wt, val, crr_cap, n - 1)

        if wt[n - 1] <= crr_cap:
            a = val[n - 1] + self.knapsack(wt, val, crr_cap - wt[n - 1], n - 1)
            """
            Added new line
            Adding the value to the cache
            """
            self.dp[n][crr_cap] = max(a, b)
            return max(a,b)
        
        else:
            """
            Added new line
            Adding the value to the cache
            """
            self.dp[n][crr_cap] = b
            return b
        
    def getMaximumvalue(self, weight, value, capacity) -> int:

        ret = self.knapsack(weight, value, capacity, len(weight))
        return ret


a = Solution()
"""
Constraints:
len(weight) <= 10 (n)
capacity <= 20 (crr_cap)

Note:
a.dp is a matrix with [capacity + 1][len(weight) + 1]
"""
weight = [1, 2, 3, 4, 5, 6]
value = [4, 5, 6, 7, 8, 9]
a.dp = [[-1] * (20 + 2)] * (len(weight) + 2)

两个程序的输入：

output = a.getMaximumvalue(weight, value, 0)
print(output)

output = a.getMaximumvalue(weight, value, 2)
print(output)

output = a.getMaximumvalue(weight, value, 4)
print(output)

output = a.getMaximumvalue(weight, value, 6)
print(output)

output = a.getMaximumvalue(weight, value, 8)
print(output)

output = a.getMaximumvalue(weight, value, 10)
print(output)

output = a.getMaximumvalue(weight, value, 12)
print(output)

output = a.getMaximumvalue(weight, value, 14)
print(output)

output = a.getMaximumvalue(weight, value, 16)
print(output)

output = a.getMaximumvalue(weight, value, 18)
print(output)

output = a.getMaximumvalue(weight, value, 20)
print(output)

的输出

0
5
10
15
17
22
24
26
31
33
35

第二个程序的第一个程序输出

0
5
10
15
20
25
30
35
40
45
50

，但该代码为某些输入提供了不同的输出。第二个程序的错误是什么？

Answer 1

问题是创建a.dp。

a.dp = [[-1] * (20 + 2)] * (len(weight) + 2)

这会导致上述问题 tery：list-lists-lists-lists-list-list-list-changes-change-changected-reflected refrefected-reflected-reflected-reflected -Across-sublists-Ablectly

解决此问题的解决方案使用以下代码来声明和初始化列表。

a.dp = []

for i in range(b):
    tmp = []
    for j in range(cap):
        tmp.append(-1)
    a.dp.append(tmp)