解决硬币找零问题时字典内容的意外更改

Question

我试图解决的问题是：给定一个硬币列表和一个总和，找出使用这些硬币形成总和的所有可能方法（你可以无限次使用一个硬币）例如：4 和 [1,2,3] 将给出答案 [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]。谁能解释一下为什么会这样，谢谢。

P.s：在这里，我的算法总是将 0 放入每个可能的组合中。

Answer 1

主要问题是这一行：

i.append(num)

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

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

还有以下问题：

下面的代码...
```
return [[0]]
```
... 将使每个组合都将包含值 0，因为它们都是通过扩展此基本情况构建的。你应该改为：
```
return [[]]
```
有了这个代码...
```
for num in numbers:
    remainder = target_sum - num
```
...您正在以累积的方式减少 remainder，即您不会撤消更改为remainder 在循环迭代结束时。相反，根本不要使用这个变量，并保持简化的表达式动态：
```
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]))

Answer 2

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

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

这可以通过执行来证明：

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

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

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

a is b

将计算为 True。重要的是要了解 is 和 == 不是相同的运算符。

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

相反，在将 num 附加到 i 之前，使用 i.copy() 将 i 复制到一个新的分离列表中，以防止 memo 中的实际数据免于更改。

而不是：

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)

解决硬币找零问题时字典内容的意外更改

Unintended changes in dictionary's content when solving the coin change problem

python

algorithm

dictionary

dynamic-programming