0

我需要为一个给定的问题编写一个算法：你有无限的便士、五分钱、一角硬币和四分之一。编写一个类方法，该方法将输出所有硬币组合，使总数为 99 美分。

这似乎是一个排列 nPr 问题。有什么算法吗？

问候， 普里扬克

4

4 回答 4

1

我认为使用递归 wa 面额表最容易回答这个问题

{5000, 2000, ... 1} // 50 美元兑换一便士

你会开始：

WaysToMakeChange(10000, 0) // ie. $100...highest denomination index is 0 ($50)

WaysToMakeChange(amount, maxdenomindex) would calculate using 0 or more of the maxdenom
the recurance is something like
WaysToMakeChange(amount - usedbymaxdenom, maxdenomindex - 1)

我对此进行了编程，可以通过多种方式对其进行优化：

1) 多线程

2）缓存。这个非常重要。算法工作方式的 B/c，WaysToMakeChange(m,n) 将使用相同的初始值多次调用：例如。更改 $100 可以通过以下方式完成：1 $50 + 0 $20's + 0 $10's + 以最高货币 $5 变为 $50 美元的方式（即 WaysToMakeChange(5000, index for $5) 0 $50 + 2 $20's + 1 $10' s +ways to $50 dollar with high currency $5 (ie. WaysToMakeChange(5000, index for $5) 显然 WaysToMakeChange(5000, index for $5) 可以被缓存，因此不需要进行后续调用

3）短路最低递归。假设 static const int denom[] = {5000, 2000, 1000, 500, 200, 100, 50, 25, 10, 5, 1};

WaysToMakeChange(int total, int coinIndex) 的第一个测试应该是这样的： if( coin[_countof(coins)-1] == 1 && coinIndex == _countof(coins) - 2){ return total / coin[_countof(硬币）-2] + 1; }

这是什么意思？好吧，如果你的最低面额是 1，那么你只需要走到第二低的面额（比如镍）。然后剩下 1+ 总/第二低的面额。例如：49c -> 5 个镍币 + 4 个便士。4 镍币 + 9 便士....49 便士 = 1+ 总数/剩下的第二个最低面额

于 2014-06-17T21:55:26.710 回答
0

这个问题似乎是一个丢番图方程，即对于 a*x + b*y + ... = n，找到一个解决方案，其中所有字母都是整数。最简单但不是最优雅的解决方案是迭代解决方案（在 python 中显示，注意我跳过变量 l 因为它类似于数字 1）：

dioph_combinations = list()
for i in range(0, 99, 25):
    for j in range(0, 99-i, 10):
        for k in range(0, 99-i-j, 5):
            for m in range(0, 99-i-j-k, 1): 
                if i + j + k + m == 99:
                    dioph_combinations.append( (i/25, j/10, k/5, m) )

结果列表 dioph_combinations 将包含可能的组合。

于 2012-06-13T09:14:25.807 回答
0

最简单的方法可能是花几分钟时间思考这个问题。有一种相对不错的递归算法，可以巧妙地用于记忆或重新加工成动态编程解决方案。

于 2012-06-13T09:15:00.870 回答
0

这个问题是经典的动态规划问题。你可以在这里读到它

http://www.algorithmist.com/index.php/Coin_Change

蟒蛇代码是：

def count( n, m ):
    if n == 0:
        return 1
    if n < 0:
        return 0
    if m <= 0 and n >= 1:
        return 0

    return count( n, m - 1 ) + count( n - S[m], m )

这里 S[m] 给出面额的值，S 是面额的排序数组

于 2012-06-13T18:37:30.237 回答