确定硬币组合的算法

Question

最近我面临了一个编程算法的提示，但我不知道该如何做。我从来没有写过算法，所以在这方面我是新手。

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

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

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

4 2 6 10 15 50 

（在这种情况下，数字对应我给出的示例）

- ahota

---

这个问题有一些对你有用的答案；https://dev59.com/pHNA5IYBdhLWcg3wEZaT - Chris McAtackney

你需要知道实际的硬币组合，还是只需要知道它们的数量？ - j_random_hacker

Answer 1

这个问题被称为硬币找零问题。请查看这里和这里了解详情。此外，如果您通过谷歌搜索“coin change”或“dynamic programming coin change”，您会得到许多其他有用的资源。

- taskinoor

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;
}

- zc22

Answer 3

这似乎有点像分区，但你没有使用1到50中的所有整数。它也类似于装箱问题，但有些不同:

• 维基百科：分区（数论）
• 维基百科：装箱问题
• 沃尔夫拉姆数学世界：分区

实际上，在考虑了一下之后，这是一个整数线性规划问题(ILP)，因此是NP难题。

我建议采用一些动态规划方法。基本上，你需要定义一个值“remainder”，并将其设置为你的目标（比如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）

- jedwards

---

你对如何解决问题的实际描述是准确的，但其余部分存在一些问题：你所描述的方法不是DP而是纯递归（这是正确的方法，因为假设我们想要完整地写出所有解集，DP在这里并没有什么用处）。任何具有离散解的问题都可以被表述为ILP——这并不意味着NP难度。我看不出与装箱问题之间的联系。 - j_random_hacker

实际上，我认为我误读了问题——似乎OP只想知道更改可能发生的次数。在这种情况下，DP确实是可能和有用的：对于每个硬币大小c和更改金额a的组合，您可以记录使用大小不超过c的硬币制作a的不同方法的数量。（需要一个2D DP矩阵来避免重复计算解决方案。） - j_random_hacker

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的不同方式
• 总结所有结果，这些结果当然是不同的（在第一个中没有使用15美分硬币，在第二个中使用了一个，在第三个中使用了两个，在第四个中使用了三个）。

因此，你基本上可以将问题分解为较小的问题（可能是更少的硬币和更少的金额）。当你只有一种硬币类型时，答案当然是微不足道的（要么无法精确达到规定金额，要么只有一种可能的方式）。

此外，你还可以通过使用记忆化来避免重复计算，例如仅使用[6, 2]达到20的方式的数量不取决于已经支付的30是否使用了15+15或10+10+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])

- 6502

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将包含可能的硬币值。

- Björn Pollex

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;
}

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

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

- Klark

Answer 7

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

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)
}

- mikedanylov

Answer 8

一个比较笨的方法是，你可以构建一个“价值为X的硬币被使用Y次”的映射关系，然后枚举所有可能的组合，只选择总和为所需的金额的组合。显然，对于每个硬币价值X，你需要检查Y是否在0到所需的总和之间。虽然这个方法会比较慢，但它能够解决你的问题。

- sharptooth

Answer 9

这很类似于背包问题

- Dmitry

---

我认为不是这样。在背包问题中，你尝试最大化价值，但在这种情况下你没有价值，你不是在尝试最大化任何东西，而是要精确地达到给定的限制。 - Björn Pollex

Answer 10

你需要解决以下方程：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），然后根据当前 d 的值开始给 c 赋予所有可能的值，以此类推。

- RaduK