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

Question

我试图解决的问题是：给出一个硬币列表和一个和，找出使用这些硬币形成和的所有可能方法(你可以使用一个硬币无限长的时间(例如：4和[1，2，3]将给出答案[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

主要问题是这一行：

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

将评估为CCD_ 12。重要的是要理解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)