1

也许我误读了这个问题。对于那些不熟悉Project Euler 的问题 31 的人，这里是问题：

调查英国货币面额的组合。

在英格兰，货币由英镑、英镑和便士组成，一般流通的硬币有八种：

1p、2p、5p、10p、20p、50p、1 英镑（100 便士）和 2 英镑（200 便士）。

可以通过以下方式赚取 2 英镑：

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

使用任意数量的硬币可以通过多少种不同的方式制作 2 英镑？

我知道这可能是一个动态编程问题，但我不禁走捷径：

为了解决这个问题，我分解了使用 1p、1p 和 2p 以及 1p、2p 和 5p 硬币可以制作 1 到 6 便士的方法。

仅使用一便士硬币

  1. 1个组合
    • 1便士
  2. 1个组合
    • 2×1p
  3. 1个组合
    • 3×1p
  4. 1个组合
    • 4×1p
  5. 1个组合
    • 5×1p
  6. 1个组合
    • 6×1p

仅使用一便士和两便士硬币

  1. 1个组合
    • 1便士
  2. 2种组合
    • 2p
    • 2×1p
  3. 2种组合
    • 2便士+1便士
    • 3×1p
  4. 3种组合
    • 2×2p
    • 2p + 2×1p
    • 4×1p
  5. 3种组合
    • 2×2p + 1p
    • 2p + 3×1p
    • 5×1p
  6. 4种组合
    • 3×2p
    • 2×2p + 2×1p
    • 2p + 4×2p
    • 6×2p

仅使用一便士、两便士和五便士硬币

  1. 1 组合
    • 1便士
  2. 2种组合
    • 2p
    • 2×1p
  3. 2种组合
    • 2便士+1便士
    • 3×1p
  4. 3种组合
    • 2×2p
    • 2p + 2×1p
    • 4×1p
  5. 4种组合
    • 5便士
    • 2×2p + 1p
    • 2p + 3×1p
    • 5×1p
  6. 5种组合
    • 5便士+1便士
    • 3×2p
    • 2×2p + 2×1p
    • 2p + 4×2p
    • 6×2p

我注意到这种疯狂是有规律的。显然，最多只有一种方法可以仅用一种硬币获得所需的“余额”。对于这个问题的情况，没有必要考虑一分钱。因此，仅使用一美分硬币，只有一种方法可以获得任何非负余额。请注意，只有一种方法可以获得零余额：没有硬币。

快速浏览了一下，我注意到第二个示例中的模式。可能组合的数量等于 n / 2 加 1 的商，其中 n 是任何非负整数。在 Python（我编写解决方案时使用的语言）中，如下所示：

n // 2 + 1

我注意到这+ 1是为特定的“目标余额”添加上一个示例的结果。巧合？也许。但是在查看第三个示例后，我很快注意到可能的组合数量如下：

n // 5 + n // 2 + 1

我实现了这个模式，它将占所有八个硬币：

n // 200 + n // 100 + n // 50 + n // 20 + n // 10 + n // 5 + n // 2 + 1

设置为 200，我推断答案是 178。这个n数字对我来说是有意义的，不过，我不会自己写出所有可能的组合。然而，Project Euler 指出这是不正确的。

我在网上发现正确的解决方案是 73682。

所以我的问题是，仍在阅读的 Stack Overflow 用户，我的推理中的谬误在哪里？

4

1 回答 1

6

仅使用 [1, 2, 5] 制作 10p 的正确组合数是 10，而您的解决方案给出 10 / 5 + 10 / 2 + 1 = 2 + 5 + 1 = 8。显然你的假设是不正确的。

错误在于您只是在尝试一些案例，并假设适用于少数小案例的方法适用于所有案例，而没有任何证据。

于 2012-08-30T07:29:01.993 回答