解决硬币变化问题时字典内容的意外变化

Question

我试图解决的问题是：给定一个硬币列表和一个总和，找出所有可能的方法来使用这些硬币形成总和（你可以无限时间使用一个硬币），例如：4和[1,2,3]将给出答案[1,1,1,1,1]，[1,1,2]，[2,2]，[1,3]（这里有三种类型的硬币，价值为1,2和3）。以下是我对这个问题的尝试：

def coin_check(target_sum, numbers):
    memo = {}

    def helper(target_sum, numbers):
        if target_sum == 0:
            return [[0]]
        if target_sum in memo:
            return memo[target_sum]
        memo[target_sum] = []
        for num in numbers:
            remainder = target_sum - num
            if remainder >= 0:
                combination = helper(remainder, numbers)
                if combination != []:
                    for i in combination:
                        i.append(num)
                        memo[target_sum].append(i)
        print(memo)
        return memo[target_sum]
    return helper(target_sum, numbers)
print(coin_check(4,[1,2,3]))

在这里，我尝试使用动态编程来跟踪我已经尝试过的值。我得到的答案是：

[[0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 2, 1, 1, 2], [0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 3, 1], [0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 2, 1, 1, 2], [0, 1, 1, 1, 
2, 1, 1, 2, 3]]

这当然是错误的。程序运行后备忘录的演变为：

{4: [], 3: [], 2: [], 1: [[0, 1]]}
{4: [], 3: [], 2: [[0, 1, 1], [0, 2]], 1: [[0, 1, 1]]}
{4: [], 3: [[0, 1, 1, 1, 2], [0, 2, 1], [0, 1, 1, 1, 2], [0, 3]], 2: [[0, 1, 1, 1, 2], [0, 2, 1]], 1: [[0, 1, 1, 1, 2]]}
{4: [[0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 2, 1, 1, 2], [0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 3, 1], [0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 2, 1, 1, 2], [0, 1, 1, 1, 2, 1, 1, 2, 3]], 3: [[0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 2, 1, 1, 2], [0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 3, 1]], 2: [[0, 1, 1, 1, 2, 1, 1, 2, 3], [0, 2, 1, 1, 2]], 1: [[0, 1, 1, 1, 2, 1, 1, 2, 3]]}

这让我感到困惑，因为我看不出我在程序中说了什么，在[0,1]已经存在之后，将memo[1]的值更改为[0,1,1]。谁能给我解释一下为什么会这样，谢谢。

这里，我的算法总是在每一个可能的组合中加0。

Answer 1

在代码段的第16行中，当您将num附加到每个可能的余数组合时，您实际上是直接更改了存储在memo中的列表。

这是因为在python中，当您获取一个列表并将其存储在变量中时，该变量实际上在内存中保存一个指向该列表地址的指针，而不是列表的副本。

这可以通过执行以下命令来证明：

a = [1, 2]
b = a
b.append(3)
print(a)

您会注意到输出是[1,2,3]，因为b实际上包含指向列表的指针，而不是列表的副本。内存中仍然只有一个列表。

一个有用的检查是使用is来评估列表。如果a和b指向内存中的相同列表，则

a是b

将计算为True。重要的是要理解是和==不是同一个运算符。

回到问题上来，这意味着每当i被更改时，memo中的条目也会被更改，因为composition实际上是指向memo中列表的指针列表。这显然是你想要避免的。

相反，在将num添加到i之前，请使用i.copy（）将i复制到一个新的分离列表中，以防止更改备忘录中的实际数据。

而不是：

for i in combination:
    i.append(num)
    memo[target_sum].append(i)

尝试：

for i in combination:
    j = i.copy()
    j.append(num)
    memo[target_sum].append(j)

Answer 2

主要问题是这一行：

i.append(num)

这会改变一个列表，该列表可能已经在更深层次的递归调用中放入memo。您应该创建一个新列表：

memo[target_sum].append(i + [num])

还有以下问题：

>

下面的代码。。。

return [[0]]

...将使每个组合都包含值0，因为它们都是通过扩展此基本情况构建的。相反，你应该这样做：

return [[]]

使用此代码。。。

for num in numbers:
    remainder = target_sum - num

... 您正在以累加的方式减少余数，即在循环迭代结束时不撤消对余数的更改。相反，根本不使用此变量，并使简化表达式保持动态：

for num in numbers:
    if target_sum >= num:
        combination = helper(target_sum - num, numbers)

有了这些修正，你就会得到一个更合理的结果。

只缺一件事：一个解的所有排列也包括在内。由于您希望排除这些硬币，您需要告诉递归调用，从哪个硬币开始可以选择硬币。这需要更多的变化，但它可以看起来像这样：

def coin_check(target_sum, numbers):
    memo = {}

    def helper(target_sum, mincoin):
        if target_sum == 0:
            return [[]]
        if target_sum in memo:
            # get memo, but only return combis that obey mincoin restriction
            return [row for row in memo[target_sum] if row[0] >= mincoin]
        memo[target_sum] = []
        for coinid in range(mincoin, len(numbers)):
            num = numbers[coinid]
            if target_sum >= num:
                combination = helper(target_sum - num, coinid)
                if combination != []:
                    for combi in combination:
                        # prefix with coinid
                        memo[target_sum].append([coinid] + combi)
        return memo[target_sum]
    
    # Convert coin id to coin value
    return [
        [numbers[coinid] for coinid in combi] 
            for combi in helper(target_sum, 0)
    ]


print(coin_check(4, [1, 2, 3]))