确定硬币组合的算法

Question

最近，我遇到了一个关于编程算法的提示，但我不知道该怎么做。我以前从未真正编写过算法，所以我在这方面还是个新手。

该问题要求编写一个程序来确定收银员根据硬币价值和硬币数量找零的所有可能的硬币组合。例如，一种货币可能有 4 个硬币：2 分、6 分、10 分和 15 分硬币。等于 50 美分的组合有多少种？

我使用的语言是 C++，尽管这并不重要。

编辑：这是一个更具体的编程问题，但是我如何分析 C++ 中的字符串来获取硬币值？它们在文本文档中给出

4 2 6 10 15 50 

（其中本例中的数字对应于我给出的示例）

Answer 1

这个问题被称为硬币找零问题。请检查此和此 了解详细信息。此外，如果您搜索“硬币找零”或“动态编程硬币找零”，那么您将获得许多其他有用的资源。

Answer 2

下面是 Java 中的递归解决方案：

// Usage: int[] denoms = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 };       
// System.out.println(ways(denoms, denoms.length, 200));
public static int ways(int denoms[], int index, int capacity) {
    if (capacity == 0) return 1;
    if (capacity < 0 || index <= 0 ) return 0;
    int withoutItem = ways(denoms, index - 1, capacity); 
    int withItem = ways(denoms, index, capacity - denoms[index - 1]); 
    return withoutItem + withItem;
}

Answer 3

这看起来有点像分区，只不过您没有使用 1:50 中的所有整数。它看起来也类似于装箱问题，但略有不同：

• 维基百科：分区（数论）
• 维基百科：装箱问题
• Wolfram Mathworld: Partiton

其实想了想，就是ILP，因此是 NP 困难的。

我建议一些动态编程方法。基本上，您可以定义一个值“余数”并将其设置为您的目标（例如 50）。然后，在每一步中，您都需要执行以下操作：

1. 找出剩余的硬币中可以容纳的最大硬币是多少
2. 考虑如果 (A) 包含该硬币或 (B) 不包含该硬币会发生什么。
3. 对于每个场景，递归。

因此，如果余数为 50，最大的硬币价值 25 和 10，则您将分为两种情况：

1. Remainder = 25, Coinset = 1x25
2. Remainder = 50, Coinset = 0x25

下一步（对于每个分支）可能如下所示：

1-1. Remainder = 0,  Coinset = 2x25 <-- Note: Remainder=0 => Logged
1-2. Remainder = 25, Coinset = 1x25
2-1. Remainder = 40, Coinset = 0x25, 1x10
2-2. Remainder = 50, Coinset = 0x25, 0x10

每个分支将分为两个分支，除非：

• 余数为 0（在在这种情况下你会记录它）
• 余数小于最小的硬币（在这种情况下你会丢弃它）
• 没有更多的硬币剩下（在这种情况下你会丢弃它，因为剩余！= 0）

Answer 4

如果您有 15、10、6 和 2 分硬币，并且您需要找出有多少种不同的方法可以达到 50，您可以

• 仅使用 10、6 和 2
• 来计算有多少种 不同的方法可以达到 50。仅使用 10、6 和 2 即可达到 50-15 的方法
• 计算仅使用 10、6 和 2 即可达到 50-15*2 的不同方法有多少种
• 计算如何有很多不同的方法，你只需要使用 10、6 和 2 就可以达到 50-15*3
• 总结所有这些当然不同的结果（在第一个中我没有使用 15c 硬币，在第二个中我使用了一个，在第三个中两个）以及第四个三）。

所以你基本上可以将问题分成更小的问题（可能更小的数量和更少的硬币）。当您只有一种硬币类型时，答案当然是微不足道的（要么您无法准确达到规定的金额，要么您可以通过唯一可能的方式达到）。

此外，您还可以通过使用记忆来避免重复相同的计算，例如仅使用 [6, 2] 达到 20 的方法数量并不取决于是否使用 15+15 或 10+10+ 达到已支付的 30 10，所以较小问题 (20, [6, 2]) 的结果可以
被储存和重复使用。

在Python中这个想法的实现如下

cache = {}

def howmany(amount, coins):
    prob = tuple([amount] + coins) # Problem signature
    if prob in cache:
        return cache[prob] # We computed this before
    if amount == 0:
        return 1 # It's always possible to give an exact change of 0 cents
    if len(coins) == 1:
        if amount % coins[0] == 0:
            return 1 # We can match prescribed amount with this coin
        else:
            return 0 # It's impossible
    total = 0
    n = 0
    while n * coins[0] <= amount:
        total += howmany(amount - n * coins[0], coins[1:])
        n += 1
    cache[prob] = total # Store in cache to avoid repeating this computation
    return total

print howmany(50, [15, 10, 6, 2])

Answer 5

至于问题的第二部分，假设您在文件 coins.txt 中有该字符串：

#include <fstream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::ifstream coins_file("coins.txt");
    std::vector<int> coins;
    std::copy(std::istream_iterator<int>(coins_file),
              std::istream_iterator<int>(),
              std::back_inserter(coins));
}

现在向量 coins 将包含可能的硬币值。

Answer 6

对于如此少量的硬币，您可以编写一个简单的暴力解决方案。

像这样的东西：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> v;

int solve(int total, int * coins, int lastI)
{
    if (total == 50) 
    {
        for (int i = 0; i < v.size(); i++)
        {
            cout << v.at(i) << ' ';
        }
        cout << "\n";
        return 1;
    }

    if (total > 50) return 0;

    int sum = 0;

    for (int i = lastI; i < 6; i++)
    {
        v.push_back(coins[i]);
        sum += solve(total + coins[i], coins, i); 
        v.pop_back();
    }

    return sum;
}


int main()
{
    int coins[6] = {2, 4, 6, 10, 15, 50};
    cout << solve(0, coins, 0) << endl;
}

一个非常肮脏的暴力解决方案，打印所有可能的组合。

这是一个非常著名的问题，因此请尝试阅读其他人提供的更好的解决方案。

Answer 7

一种相当愚蠢的方法如下。您构建一个映射“价值 X 的硬币被使用 Y 次”，然后枚举所有可能的组合，并仅选择那些总计达到所需总和的组合。显然，对于每个值 X，您必须检查 Y 的范围从 0 到所需的总和。这会相当慢，但会解决你的任务。

Answer 8

它与背包问题非常相似

Answer 9

您基本上必须求解以下方程：50 = a*4 + b*6 + c*10 + d*15，其中未知数为 a、b、c、d。例如，您可以计算每个变量的 d = (50 - a*4 - b*6 - c*10)/15 等。然后，你开始给 d 所有可能的值（你应该从具有最小可能值的那个开始，这里是 d）：0,1,2,3,4，然后根据当前的情况开始给 c 所有可能的值d 的值等等。

Answer 10

将列表向后排序：[15 10 6 4 2]

现在 50 克拉的解决方案可以包含或不包含 15 克拉。
因此，解决方案的数量是使用 [10 6 4 2] 的 50 克拉的解决方案数量（不再考虑 15 克拉硬币）加上 使用的 35 克拉 (=50ct - 15ct) 的解决方案数量[15 10 6 4 2]。对两个子问题重复该过程。

Answer 11

算法是解决问题的过程，它不必采用任何特定的语言。

首先计算出输入：

typedef int CoinValue;

set<CoinValue> coinTypes;
int value;

和输出：

set< map<CoinValue, int> > results;

首先解决您能想到的最简单的情况：

coinTypes = { 1 }; // only one type of coin worth 1 cent
value = 51;

结果应该是：

results = { [1 : 51] }; // only one solution, 51 - 1 cent coins

您将如何解决上述问题？

这个怎么样：

coinTypes = { 2 };
value = 51;

results = { }; // there is no solution

这个怎么样？

coinTypes = { 1, 2 };
value = { 4 };

results = { [2: 2], [2: 1, 1: 2], [1: 4] }; // the order I put the solutions in is a hint to how to do the algorithm.

Answer 12

基于 Scala 中的 algorithmist.com 资源的递归解决方案：

def countChange(money: Int, coins: List[Int]): Int = {
    if (money < 0 || coins.isEmpty) 0
    else if (money == 0) 1
    else countChange(money, coins.tail) + countChange(money - coins.head, coins)
}

Answer 13

另一个Python版本：

def change(coins, money):
    return (
        change(coins[:-1], money) +
        change(coins, money - coins[-1])
        if money > 0 and coins
        else money == 0
    )