时间戳

首页 > 解决方案 > 修复硬币变化蛮力解决方案

python - 修复硬币变化蛮力解决方案

问题描述

我开始写作并理解硬币找零问题，但无法获得直觉，所以我开始写一个蛮力解决方案。在进行记忆之前，我想了解蛮力解决方案。

coins = [2, 3, 7]
change = 12

def coin_change(c):
    print(c)
    if c <= 0:
        return 0
    else:
        for i in coins:
            if c - i >= 0:
                coin_change(c - i)

coin_change(change)

它打印出剩下的几个更改，但我不知道如何将每个路径存储在数组中。

我还想了解如何使用递归来跟踪路径。我可以考虑在其中添加一个额外的参数，coin_change但也许还有另一种方法。

我对它的复杂性感到困惑。它每一步都有许多硬币调用，但许多在线资源提到它是 2 n。

编辑：请注意硬币供应是无限的，答案是4

[2, 2, 2, 2, 2, 2]
[3, 3, 3, 3]
[2, 2, 2, 3, 3]
[2, 3, 7]

标签： pythonrecursion

解决方案

了解硬币找零问题：

假设您指的是用最少数量的硬币计算零钱的问题，这里的关键思想是将问题视为在每一步中做出选择——在这种情况下是“下一步要分配什么硬币？”

您可以将问题分解为您拥有的硬币coin_change(score) = 1 + min{coin_change(score - c1), coin_change(score - c2), ...}在哪里。c1, c2...

跟踪路径：

这是相当简单的。而不是返回解决方案（最小硬币组合），只需返回所有可能性（所有硬币组合）。因此，当您对 (score-c1) 进行递归调用时，您将获得所有构成 (score-c1) 的硬币组合，然后您只需将 c1 添加到它们。

编码

coins = [2, 3, 7]
change = 12

def coin_change(c):
  if c == 0:
    return [[]]     # the only combo possible is no coins
  if c < 0:
    return []      # no combos possible
  else:
    all_combos = []
    for i in coins:
      recursive_result = coin_change(c-i)
      for combo in recursive_result:
        combo.append(i)
      all_combos.extend(recursive_result)

    return all_combos

result = coin_change(change)
for combo in result:
  print(combo)

注意：这将为您提供所有排列。如果顺序无关紧要，您可以使用集合来删除重复项

编辑：在评论之后，这是删除重复项的代码

coins = [2, 3, 7]
change = 12

def removeDuplicates(combos):
  filtered = set()
  for combo in combos:
    combo.sort()
    filtered.add(tuple(combo))
  return [list(i) for i in filtered]

def coin_change(c):
  if c == 0:
    return [[]]     # the only combo possible is no coins
  if c < 0:
    return []      # no combos possible
  else:
    all_combos = []
    for i in coins:
      recursive_result = coin_change(c-i)
      for combo in recursive_result:
        combo.append(i)
      all_combos.extend(recursive_result)

    return removeDuplicates(all_combos)

result = coin_change(change)
for combo in result:
  print(combo)

推荐阅读