How to find all combinations of coins when given some dollar value

Both: iterate through all denominations from high to low, take one of denomination, subtract from requried total, then recurse on remainder (constraining avilable denominations to be equal or lower to current iteration value.)

设 C (i，J)使用集合 J 中的值使 i 分的组合集合。

你可以这样定义 C:

(首先(J)取 以一种确定的方式集合的一个元素)

It turns out a pretty recursive function... and reasonably efficient if you use memoization ;)

我倾向于使用递归解决方案。你有一些面值的列表，如果最小的一个可以均匀地除以任何剩余的货币金额，这应该工作的很好。

基本上，你从最大的面额转移到最小的面额。
Recursively,

1. 您有一个当前总额要填写，并且有一个最大面额(还剩1个以上)。 如果只剩下1个面额，只有一种方法可以填补总额。您可以使用当前面值的0到 k 个副本，使得 k * cur 面值 < = total。
2. 对于0到 k，调用具有修改过的 total 和 new 最大面值的函数。
3. 把结果从0加到 k。这就是从当前面值开始，你可以用多少种方法来填满你的总数。回这个号码。

这是我的蟒蛇版本的问题，200美分。我有1463种方法。此版本打印所有组合和最终计数总数。

#!/usr/bin/python


# find the number of ways to reach a total with the given number of combinations


cents = 200
denominations = [25, 10, 5, 1]
names = {25: "quarter(s)", 10: "dime(s)", 5 : "nickel(s)", 1 : "pennies"}


def count_combs(left, i, comb, add):
if add: comb.append(add)
if left == 0 or (i+1) == len(denominations):
if (i+1) == len(denominations) and left > 0:
if left % denominations[i]:
return 0
comb.append( (left/denominations[i], demoninations[i]) )
i += 1
while i < len(denominations):
comb.append( (0, denominations[i]) )
i += 1
print(" ".join("%d %s" % (n,names[c]) for (n,c) in comb))
return 1
cur = denominations[i]
return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))


count_combs(cents, 0, [], None)

解决独特的组合问题-力量递减顺序:

$denoms = [1,5,10,25]
def all_combs(sum,last)
return 1 if sum == 0
return $denoms.select{|d| d &le sum && d &le last}.inject(0) {|total,denom|
total+all_combs(sum-denom,denom)}
end

这将运行缓慢，因为它不会被记录，但你得到的想法。

这里有一些绝对简单的 C + + 代码来解决这个问题，它要求显示所有的组合。

#include <stdio.h>
#include <stdlib.h>


int main(int argc, char *argv[])
{
if (argc != 2)
{
printf("usage: change amount-in-cents\n");
return 1;
}


int total = atoi(argv[1]);


printf("quarter\tdime\tnickle\tpenny\tto make %d\n", total);


int combos = 0;


for (int q = 0; q <= total / 25; q++)
{
int total_less_q = total - q * 25;
for (int d = 0; d <= total_less_q / 10; d++)
{
int total_less_q_d = total_less_q - d * 10;
for (int n = 0; n <= total_less_q_d / 5; n++)
{
int p = total_less_q_d - n * 5;
printf("%d\t%d\t%d\t%d\n", q, d, n, p);
combos++;
}
}
}


printf("%d combinations\n", combos);


return 0;
}

但是我对计算组合数的子问题很感兴趣。我怀疑这里有一个封闭的方程式。

If the currency system allows it, a simple greedy algorithm that takes as many of each coin as possible, starting with the highest value currency.

否则，动态规划需要找到一个最佳的解决方案，因为这个问题本质上是 背包问题。

例如，如果一个货币系统有这样一个硬币: {13, 8, 1}，贪婪的解决方案将把24改为 {13, 8, 1, 1, 1}，但是真正的最佳解决方案是 {8, 8, 8}

编辑: 我认为我们正在做出最佳的改变，而不是列出所有的方法来改变一美元。我最近的面试问到如何做出改变，所以我在读完这个问题之前就跳过了。

我现在觉得自己很蠢。下面是一个过于复杂的解决方案，我将保留它，因为它毕竟是 是解决方案。一个简单的解决办法是:

// Generate a pretty string
val coinNames = List(("quarter", "quarters"),
("dime", "dimes"),
("nickel", "nickels"),
("penny", "pennies"))
def coinsString =
Function.tupled((quarters: Int, dimes: Int, nickels:Int, pennies: Int) => (
List(quarters, dimes, nickels, pennies)
zip coinNames // join with names
map (t => (if (t._1 != 1) (t._1, t._2._2) else (t._1, t._2._1))) // correct for number
map (t => t._1 + " " + t._2) // qty name
mkString " "
))


def allCombinations(amount: Int) =
(for{quarters <- 0 to (amount / 25)
dimes <- 0 to ((amount - 25*quarters) / 10)
nickels <- 0 to ((amount - 25*quarters - 10*dimes) / 5)
} yield (quarters, dimes, nickels, amount - 25*quarters - 10*dimes - 5*nickels)
) map coinsString mkString "\n"

这是另一个解决办法。这个解决方案是基于这样的观察: 每个硬币都是其他硬币的倍数，因此它们可以用它们来表示。

// Just to make things a bit more readable, as these routines will access
// arrays a lot
val coinValues = List(25, 10, 5, 1)
val coinNames = List(("quarter", "quarters"),
("dime", "dimes"),
("nickel", "nickels"),
("penny", "pennies"))
val List(quarter, dime, nickel, penny) = coinValues.indices.toList




// Find the combination that uses the least amount of coins
def leastCoins(amount: Int): Array[Int] =
((List(amount) /: coinValues) {(list, coinValue) =>
val currentAmount = list.head
val numberOfCoins = currentAmount / coinValue
val remainingAmount = currentAmount % coinValue
remainingAmount :: numberOfCoins :: list.tail
}).tail.reverse.toArray


// Helper function. Adjust a certain amount of coins by
// adding or subtracting coins of each type; this could
// be made to receive a list of adjustments, but for so
// few types of coins, it's not worth it.
def adjust(base: Array[Int],
quarters: Int,
dimes: Int,
nickels: Int,
pennies: Int): Array[Int] =
Array(base(quarter) + quarters,
base(dime) + dimes,
base(nickel) + nickels,
base(penny) + pennies)


// We decrease the amount of quarters by one this way
def decreaseQuarter(base: Array[Int]): Array[Int] =
adjust(base, -1, +2, +1, 0)


// Dimes are decreased this way
def decreaseDime(base: Array[Int]): Array[Int] =
adjust(base, 0, -1, +2, 0)


// And here is how we decrease Nickels
def decreaseNickel(base: Array[Int]): Array[Int] =
adjust(base, 0, 0, -1, +5)


// This will help us find the proper decrease function
val decrease = Map(quarter -> decreaseQuarter _,
dime -> decreaseDime _,
nickel -> decreaseNickel _)


// Given a base amount of coins of each type, and the type of coin,
// we'll produce a list of coin amounts for each quantity of that particular
// coin type, up to the "base" amount
def coinSpan(base: Array[Int], whichCoin: Int) =
(List(base) /: (0 until base(whichCoin)).toList) { (list, _) =>
decrease(whichCoin)(list.head) :: list
}


// Generate a pretty string
def coinsString(base: Array[Int]) = (
base
zip coinNames // join with names
map (t => (if (t._1 != 1) (t._1, t._2._2) else (t._1, t._2._1))) // correct for number
map (t => t._1 + " " + t._2)
mkString " "
)


// So, get a base amount, compute a list for all quarters variations of that base,
// then, for each combination, compute all variations of dimes, and then repeat
// for all variations of nickels.
def allCombinations(amount: Int) = {
val base = leastCoins(amount)
val allQuarters = coinSpan(base, quarter)
val allDimes = allQuarters flatMap (base => coinSpan(base, dime))
val allNickels = allDimes flatMap (base => coinSpan(base, nickel))
allNickels map coinsString mkString "\n"
}

比如说37枚硬币:

scala> println(allCombinations(37))
0 quarter 0 dimes 0 nickels 37 pennies
0 quarter 0 dimes 1 nickel 32 pennies
0 quarter 0 dimes 2 nickels 27 pennies
0 quarter 0 dimes 3 nickels 22 pennies
0 quarter 0 dimes 4 nickels 17 pennies
0 quarter 0 dimes 5 nickels 12 pennies
0 quarter 0 dimes 6 nickels 7 pennies
0 quarter 0 dimes 7 nickels 2 pennies
0 quarter 1 dime 0 nickels 27 pennies
0 quarter 1 dime 1 nickel 22 pennies
0 quarter 1 dime 2 nickels 17 pennies
0 quarter 1 dime 3 nickels 12 pennies
0 quarter 1 dime 4 nickels 7 pennies
0 quarter 1 dime 5 nickels 2 pennies
0 quarter 2 dimes 0 nickels 17 pennies
0 quarter 2 dimes 1 nickel 12 pennies
0 quarter 2 dimes 2 nickels 7 pennies
0 quarter 2 dimes 3 nickels 2 pennies
0 quarter 3 dimes 0 nickels 7 pennies
0 quarter 3 dimes 1 nickel 2 pennies
1 quarter 0 dimes 0 nickels 12 pennies
1 quarter 0 dimes 1 nickel 7 pennies
1 quarter 0 dimes 2 nickels 2 pennies
1 quarter 1 dime 0 nickels 2 pennies

我很久以前研究过这个，你可以看看我的 小小的报道，这是 Mathematica 资源。

通过使用生成函数，可以得到该问题的闭式常数时间解。Graham，Knuth 和 Patashnik 的 具体数学就是这方面的书，包含了对这个问题相当广泛的讨论。本质上，你定义了一个多项式，其中的 N系数是 N美元的变化方式的数量。

这篇文章的第4-5页展示了如何使用 Mathematica (或任何其他方便的计算机代数系统)在几秒钟内用三行代码计算出10 ^ 10 ^ 6美元的答案。

(这已经是很久以前的事情了，在75Mhz 的奔腾上只有几秒钟的时间... ...)

我的这个博客条目 为 XKCD 漫画的数字解决了这个类似背包的问题。对 items和 exactcost值的一个简单更改也将产生所有解决您的问题的方案。

如果问题是找到使用最少成本的变化，那么一个幼稚的贪婪算法，使用尽可能多的最高价值的硬币很可能失败的硬币和目标金额的某些组合。例如，如果有值为1、3和4的硬币，而目标金额是6，那么贪婪算法可能会建议使用值为4、1和1的三个硬币，因为很容易看出你可以使用每个值为3的两个硬币。

• 帕迪。

我用一个非常简单的循环来解决这个问题，在 BlackJack 游戏中，我使用等基因游戏引擎用 HTML5编写。你可以看到一个视频的黑杰克游戏，显示了筹码，用于组成赌注从赌注价值的黑杰克表上方的卡: http://bit.ly/yUF6iw

在这个例子中，betValue 等于您希望分成“硬币”或“筹码”或其他任何东西的总值。

您可以将 chipValue 数组项设置为您的硬币或芯片的价值。确保订购的物品从最低价值到最高价值(一便士，五分镍币，一角硬币，四分之一)。

以下是 JavaScript:

// Set the total that we want to divide into chips
var betValue = 191;


// Set the chip values
var chipValues = [
1,
5,
10,
25
];


// Work out how many of each chip is required to make up the bet value
var tempBet = betValue;
var tempChips = [];
for (var i = chipValues.length - 1; i >= 0; i--) {
var chipValue = chipValues[i];
var divided = Math.floor(tempBet / chipValue);


if (divided >= 1) {
tempChips[i] = divided;
tempBet -= divided * chipValues[i];
}


if (tempBet == 0) { break; }
}


// Display the chips and how many of each make up the betValue
for (var i in tempChips) {
console.log(tempChips[i] + ' of ' + chipValues[i]);
}

显然，您不需要执行最后一个循环，它只是用来记录 console.log 最终数组值的。

Scala function :

def countChange(money: Int, coins: List[Int]): Int = {


def loop(money: Int, lcoins: List[Int], count: Int): Int = {
// if there are no more coins or if we run out of money ... return 0
if ( lcoins.isEmpty || money < 0) 0
else{
if (money == 0 ) count + 1
/* if the recursive subtraction leads to 0 money left - a prefect division hence return count +1 */
else
/* keep iterating ... sum over money and the rest of the coins and money - the first item and the full set of coins left*/
loop(money, lcoins.tail,count) + loop(money - lcoins.head,lcoins, count)
}
}


val x = loop(money, coins, 0)
Console println x
x
}

我知道这是个很古老的问题。我一直在寻找正确的答案，但找不到任何简单和令人满意的答案。我花了点时间，但还是记下了一些东西。

function denomination(coins, original_amount){
var original_amount = original_amount;
var original_best = [ ];


for(var i=0;i<coins.length; i++){
var amount = original_amount;
var best = [ ];
var tempBest = [ ]
while(coins[i]<=amount){
amount = amount - coins[i];
best.push(coins[i]);
}
if(amount>0 && coins.length>1){
tempBest = denomination(coins.slice(0,i).concat(coins.slice(i+1,coins.length)), amount);
//best = best.concat(denomination(coins.splice(i,1), amount));
}
if(tempBest.length!=0 || (best.length!=0 && amount==0)){
best = best.concat(tempBest);
if(original_best.length==0 ){
original_best = best
}else if(original_best.length > best.length ){
original_best = best;
}
}
}
return original_best;
}
denomination( [1,10,3,9] , 19 );

这是一个使用递归的 javascript 解决方案。

子问题是一个典型的动态规划问题。

/* Q: Given some dollar value in cents (e.g. 200 = 2 dollars, 1000 = 10 dollars),
find the number of combinations of coins that make up the dollar value.
There are only penny, nickel, dime, and quarter.
(quarter = 25 cents, dime = 10 cents, nickel = 5 cents, penny = 1 cent) */
/* A:
Reference: http://andrew.neitsch.ca/publications/m496pres1.nb.pdf
f(n, k): number of ways of making change for n cents, using only the first
k+1 types of coins.


+- 0,                        n < 0 || k < 0
f(n, k) = |- 1,                        n == 0
+- f(n, k-1) + f(n-C[k], k), else
*/


#include <iostream>
#include <vector>
using namespace std;


int C[] = {1, 5, 10, 25};


// Recursive: very slow, O(2^n)
int f(int n, int k)
{
if (n < 0 || k < 0)
return 0;


if (n == 0)
return 1;


return f(n, k-1) + f(n-C[k], k);
}


// Non-recursive: fast, but still O(nk)
int f_NonRec(int n, int k)
{
vector<vector<int> > table(n+1, vector<int>(k+1, 1));


for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= k; ++j)
{
if (i < 0 || j < 0) // Impossible, for illustration purpose
{
table[i][j] = 0;
}
else if (i == 0 || j == 0) // Very Important
{
table[i][j] = 1;
}
else
{
// The recursion. Be careful with the vector boundary
table[i][j] = table[i][j-1] +
(i < C[j] ? 0 : table[i-C[j]][j]);
}
}
}


return table[n][k];
}


int main()
{
cout << f(100, 3) << ", " << f_NonRec(100, 3) << endl;
cout << f(200, 3) << ", " << f_NonRec(200, 3) << endl;
cout << f(1000, 3) << ", " << f_NonRec(1000, 3) << endl;


return 0;
}

这是一个非常古老的问题，但是我想出了一个用 java 递归的解决方案，它看起来比其他所有方案都要小，所以我们开始吧-

 public static void printAll(int ind, int[] denom,int N,int[] vals){
if(N==0){
System.out.println(Arrays.toString(vals));
return;
}
if(ind == (denom.length))return;
int currdenom = denom[ind];
for(int i=0;i<=(N/currdenom);i++){
vals[ind] = i;
printAll(ind+1,denom,N-i*currdenom,vals);
}
}

改善措施:

  public static void printAllCents(int ind, int[] denom,int N,int[] vals){
if(N==0){
if(ind < denom.length) {
for(int i=ind;i<denom.length;i++)
vals[i] = 0;
}
System.out.println(Arrays.toString(vals));
return;
}
if(ind == (denom.length)) {
vals[ind-1] = 0;
return;
}


int currdenom = denom[ind];
for(int i=0;i<=(N/currdenom);i++){
vals[ind] = i;
printAllCents(ind+1,denom,N-i*currdenom,vals);
}
}

注意 : 这只显示了方法的数量。

Scala 函数:

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

# short and sweet with O(n) table memory


#include <iostream>
#include <vector>


int count( std::vector<int> s, int n )
{
std::vector<int> table(n+1,0);


table[0] = 1;
for ( auto& k : s )
for(int j=k; j<=n; ++j)
table[j] += table[j-k];


return table[n];
}


int main()
{
std::cout <<  count({25, 10, 5, 1}, 100) << std::endl;
return 0;
}

这是我在 Python 中的回答，它不使用递归:

def crossprod (list1, list2):
output = 0
for i in range(0,len(list1)):
output += list1[i]*list2[i]


return output


def breakit(target, coins):
coinslimit = [(target / coins[i]) for i in range(0,len(coins))]
count = 0
temp = []
for i in range(0,len(coins)):
temp.append([j for j in range(0,coinslimit[i]+1)])




r=[[]]
for x in temp:
t = []
for y in x:
for i in r:
t.append(i+[y])
r = t


for targets in r:
if crossprod(targets, coins) == target:
print targets
count +=1
return count








if __name__ == "__main__":
coins = [25,10,5,1]
target = 78
print breakit(target, coins)

输出示例

    ...
1 ( 10 cents)  2 ( 5 cents)  58 ( 1 cents)
4 ( 5 cents)  58 ( 1 cents)
1 ( 10 cents)  1 ( 5 cents)  63 ( 1 cents)
3 ( 5 cents)  63 ( 1 cents)
1 ( 10 cents)  68 ( 1 cents)
2 ( 5 cents)  68 ( 1 cents)
1 ( 5 cents)  73 ( 1 cents)
78 ( 1 cents)
Number of solutions =  121

public class Coins {


static int ac = 421;
static int bc = 311;
static int cc = 11;


static int target = 4000;


public static void main(String[] args) {




method2();
}


public static void method2(){
//running time n^2


int da = target/ac;
int db = target/bc;


for(int i=0;i<=da;i++){
for(int j=0;j<=db;j++){
int rem = target-(i*ac+j*bc);
if(rem < 0){
break;
}else{
if(rem%cc==0){
System.out.format("\n%d, %d, %d ---- %d + %d + %d = %d \n", i, j, rem/cc, i*ac, j*bc, (rem/cc)*cc, target);
}
}
}
}
}
}

代码使用 Java 来解决这个问题，而且它也工作... ... 这个方法可能不是一个好主意，因为有太多的循环，但它确实是一个直截了当的方法。

public class RepresentCents {


public static int sum(int n) {


int count = 0;
for (int i = 0; i <= n / 25; i++) {
for (int j = 0; j <= n / 10; j++) {
for (int k = 0; k <= n / 5; k++) {
for (int l = 0; l <= n; l++) {
int v = i * 25 + j * 10 + k * 5 + l;
if (v == n) {
count++;
} else if (v > n) {
break;
}
}
}
}
}
return count;
}


public static void main(String[] args) {
System.out.println(sum(100));
}
}

Java 解决方案

import java.util.Arrays;
import java.util.Scanner;




public class nCents {






public static void main(String[] args) {


Scanner input=new Scanner(System.in);
int cents=input.nextInt();
int num_ways [][] =new int [5][cents+1];


//putting in zeroes to offset
int getCents[]={0 , 0 , 5 , 10 , 25};
Arrays.fill(num_ways[0], 0);
Arrays.fill(num_ways[1], 1);


int current_cent=0;
for(int i=2;i<num_ways.length;i++){


current_cent=getCents[i];


for(int j=1;j<num_ways[0].length;j++){
if(j-current_cent>=0){
if(j-current_cent==0){
num_ways[i][j]=num_ways[i-1][j]+1;
}else{
num_ways[i][j]=num_ways[i][j-current_cent]+num_ways[i-1][j];
}
}else{
num_ways[i][j]=num_ways[i-1][j];
}




}




}






System.out.println(num_ways[num_ways.length-1][num_ways[0].length-1]);


}

}

I found this neat piece of code in the book "Python For Data Analysis" by O'reily. It uses lazy implementation and int comparison and i presume it can be modified for other denominations using decimals. Let me know how it works for you!

def make_change(amount, coins=[1, 5, 10, 25], hand=None):
hand = [] if hand is None else hand
if amount == 0:
yield hand
for coin in coins:
# ensures we don't give too much change, and combinations are unique
if coin > amount or (len(hand) > 0 and hand[-1] < coin):
continue
for result in make_change(amount - coin, coins=coins,
hand=hand + [coin]):
yield result

var countChange = function (money,coins) {
function countChangeSub(money,coins,n) {
if(money==0) return 1;
if(money<0 || coins.length ==n) return 0;
return countChangeSub(money-coins[n],coins,n) + countChangeSub(money,coins,n+1);
}
return countChangeSub(money,coins,0);
}

public static int calcCoins(int cents){
return coins(cents,new int[cents+1]);
}
public static int coins(int cents,int[] memo){
if(memo[cents] != 0){
return -1;
}
int sum = 0;
int arr[] = {25,10,5,1};


for (int i = 0; i < arr.length; i++) {
if(cents/arr[i] != 0){
int temp = coins(cents-arr[i],memo);
if(temp == 0){
sum+=1;
} else if(temp == -1){
sum +=0;
}
else{
sum += temp;
}
}
}
memo[cents] = sum;
return sum;
}

下面的 java 解决方案将打印不同的组合以及。易于理解。想法是

总和5

解决办法就是

    5 - 5(i) times 1 = 0
if(sum = 0)
print i times 1
5 - 4(i) times 1 = 1
5 - 3 times 1 = 2
2 -  1(j) times 2 = 0
if(sum = 0)
print i times 1 and j times 2
and so on......

如果每个循环中的剩余和小于面值即 如果剩下的和1小于2，那么打破循环

下面是完整的代码

如果有什么错误，请纠正我

public class CoinCombinbationSimple {
public static void main(String[] args) {
int sum = 100000;
printCombination(sum);
}


static void printCombination(int sum) {
for (int i = sum; i >= 0; i--) {
int sumCopy1 = sum - i * 1;
if (sumCopy1 == 0) {
System.out.println(i + " 1 coins");
}
for (int j = sumCopy1 / 2; j >= 0; j--) {
int sumCopy2 = sumCopy1;
if (sumCopy2 < 2) {
break;
}
sumCopy2 = sumCopy1 - 2 * j;
if (sumCopy2 == 0) {
System.out.println(i + " 1 coins " + j + " 2 coins ");
}
for (int k = sumCopy2 / 5; k >= 0; k--) {
int sumCopy3 = sumCopy2;
if (sumCopy2 < 5) {
break;
}
sumCopy3 = sumCopy2 - 5 * k;
if (sumCopy3 == 0) {
System.out.println(i + " 1 coins " + j + " 2 coins "
+ k + " 5 coins");
}
}
}
}
}

}

在 Scala 中，我会这样做:

 def countChange(money: Int, coins: List[Int]): Int = {


money match {
case 0 => 1
case x if x < 0 => 0
case x if x >= 1 && coins.isEmpty => 0
case _ => countChange(money, coins.tail) + countChange(money - coins.head, coins)


}


}

Here is a python based solution that uses recursion as well as memoization resulting in a complexity of O(mxn)

    def get_combinations_dynamic(self, amount, coins, memo):
end_index = len(coins) - 1
memo_key = str(amount)+'->'+str(coins)
if memo_key in memo:
return memo[memo_key]
remaining_amount = amount
if amount < 0:
return []
if amount == 0:
return [[]]
combinations = []
if len(coins) <= 1:
if amount % coins[0] == 0:
combination = []
for i in range(amount // coins[0]):
combination.append(coins[0])
list.sort(combination)
if combination not in combinations:
combinations.append(combination)
else:
k = 0
while remaining_amount >= 0:
sub_combinations = self.get_combinations_dynamic(remaining_amount, coins[:end_index], memo)
for combination in sub_combinations:
temp = combination[:]
for i in range(k):
temp.append(coins[end_index])
list.sort(temp)
if temp not in combinations:
combinations.append(temp)
k += 1
remaining_amount -= coins[end_index]
memo[memo_key] = combinations
return combinations

下面是蟒蛇解决方案:

    x = []
dic = {}
def f(n,r):
[a,b,c,d] = r
if not dic.has_key((n,a,b,c,d)): dic[(n,a,b,c,d)] = 1
if n>=25:
if not dic.has_key((n-25,a+1,b,c,d)):f(n-25,[a+1,b,c,d])
if not dic.has_key((n-10,a,b+1,c,d)):f(n-10,[a,b+1,c,d])
if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
elif n>=10:
if not dic.has_key((n-10,a,b+1,c,d)):f(n-10,[a,b+1,c,d])
if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
elif n>=5:
if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
elif n>=1:
if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
else:
if r not in x:
x.extend([r])


f(100, [0,0,0,0])
print x

This is the improvement of Zihan's answer. The great deal of unnecessary loops comes when the denomination is just 1 cent.

这是直观的，非递归的。

    public static int Ways2PayNCents(int n)
{
int numberOfWays=0;
int cent, nickel, dime, quarter;
for (quarter = 0; quarter <= n/25; quarter++)
{
for (dime = 0; dime <= n/10; dime++)
{
for (nickel = 0; nickel <= n/5; nickel++)
{
cent = n - (quarter * 25 + dime * 10 + nickel * 5);
if (cent >= 0)
{
numberOfWays += 1;
Console.WriteLine("{0},{1},{2},{3}", quarter, dime, nickel, cent);
}
}
}
}
return numberOfWays;
}

Straightforward java solution:

public static void main(String[] args)
{
int[] denoms = {4,2,3,1};
int[] vals = new int[denoms.length];
int target = 6;
printCombinations(0, denoms, target, vals);
}




public static void printCombinations(int index, int[] denom,int target, int[] vals)
{
if(target==0)
{
System.out.println(Arrays.toString(vals));
return;
}
if(index == denom.length) return;
int currDenom = denom[index];
for(int i = 0; i*currDenom <= target;i++)
{
vals[index] = i;
printCombinations(index+1, denom, target - i*currDenom, vals);
vals[index] = 0;
}
}

PHP 代码将金额分解为面额:

//Define the denominations
private $denominations = array(1000, 500, 200, 100, 50, 40, 20, 10, 5, 1);
/**
* S# countDenomination() function
*
* @author Edwin Mugendi <edwinmugendi@gmail.com>
*
* Count denomination
*
* @param float $original_amount Original amount
*
* @return array with denomination and count
*/
public function countDenomination($original_amount) {
$amount = $original_amount;
$denomination_count_array = array();
foreach ($this->denominations as $single_denomination) {


$count = floor($amount / $single_denomination);


$denomination_count_array[$single_denomination] = $count;


$amount = fmod($amount, $single_denomination);
}//E# foreach statement


var_dump($denomination_count_array);
return $denomination_count_array;
//return $denomination_count_array;
}

//E # count 面值()函数

这是一个简单的递归算法，它接受一张钞票，然后递归地接受一张较小的钞票，直到它达到总和，然后接受另一张面额相同的钞票，再次递归。请参阅下面的示例输出以获得说明。

var bills = new int[] { 100, 50, 20, 10, 5, 1 };


void PrintAllWaysToMakeChange(int sumSoFar, int minBill, string changeSoFar)
{
for (int i = minBill; i < bills.Length; i++)
{
var change = changeSoFar;
var sum = sumSoFar;


while (sum > 0)
{
if (!string.IsNullOrEmpty(change)) change += " + ";
change += bills[i];


sum -= bills[i];
if (sum > 0)
{
PrintAllWaysToMakeChange(sum, i + 1, change);
}
}


if (sum == 0)
{
Console.WriteLine(change);
}
}
}


PrintAllWaysToMakeChange(15, 0, "");

印刷如下:

10 + 5
10 + 1 + 1 + 1 + 1 + 1
5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
5 + 5 + 1 + 1 + 1 + 1 + 1
5 + 5 + 5
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

这里有很多变化，但是找不到一个 PHP 解决方案来处理组合的数量，所以我将添加一个。

/**
* @param int $money The total value
* @param array $coins The coin denominations
* @param int $sum The countable sum
* @return int
*/
function getTotalCombinations($money, $coins, &$sum = 0){
if ($money == 0){
return $sum++;
} else if (empty($coins) || $money < 0){
return $sum;
} else {
$firstCoin = array_pop(array_reverse($coins));
getTotalCombinations($money - $firstCoin, $coins, $sum) + getTotalCombinations($money, array_diff($coins, [$firstCoin]), $sum);
}
return $sum;
}




$totalCombinations = getTotalCombinations($money, $coins);

/*
* make a list of all distinct sets of coins of from the set of coins to
* sum up to the given target amount.
* Here the input set of coins is assumed yo be {1, 2, 4}, this set MUST
* have the coins sorted in ascending order.
* Outline of the algorithm:
*
* Keep track of what the current coin is, say ccn; current number of coins
* in the partial solution, say k; current sum, say sum, obtained by adding
* ccn; sum sofar, say accsum:
*  1) Use ccn as long as it can be added without exceeding the target
*     a) if current sum equals target, add cc to solution coin set, increase
*     coin coin in the solution by 1, and print it and return
*     b) if current sum exceeds target, ccn can't be in the solution, so
*        return
*     c) if neither of the above, add current coin to partial solution,
*        increase k by 1 (number of coins in partial solution), and recuse
*  2) When current denomination can no longer be used, start using the
*     next higher denomination coins, just like in (1)
*  3) When all denominations have been used, we are done
*/


#include <iostream>
#include <cstdlib>


using namespace std;


// int num_calls = 0;
// int num_ways = 0;


void print(const int coins[], int n);


void combine_coins(
const int denoms[], // coins sorted in ascending order
int n,              // number of denominations
int target,         // target sum
int accsum,         // accumulated sum
int coins[],        // solution set, MUST equal
// target / lowest denom coin
int k               // number of coins in coins[]
)
{


int  ccn;   // current coin
int  sum;   // current sum


// ++num_calls;


for (int i = 0; i < n; ++i) {
/*
* skip coins of lesser denomination: This is to be efficient
* and also avoid generating duplicate sequences. What we need
* is combinations and without this check we will generate
* permutations.
*/
if (k > 0 && denoms[i] < coins[k - 1])
continue;   // skip coins of lesser denomination


ccn = denoms[i];


if ((sum = accsum + ccn) > target)
return;     // no point trying higher denominations now




if (sum == target) {
// found yet another solution
coins[k] = ccn;
print(coins, k + 1);
// ++num_ways;
return;
}


coins[k] = ccn;
combine_coins(denoms, n, target, sum, coins, k + 1);
}
}


void print(const int coins[], int n)
{
int s = 0;
for (int i = 0; i < n; ++i) {
cout << coins[i] << " ";
s += coins[i];
}
cout << "\t = \t" << s << "\n";


}


int main(int argc, const char *argv[])
{


int denoms[] = {1, 2, 4};
int dsize = sizeof(denoms) / sizeof(denoms[0]);
int target;


if (argv[1])
target = atoi(argv[1]);
else
target = 8;


int *coins = new int[target];




combine_coins(denoms, dsize, target, 0, coins, 0);


// cout << "num calls = " << num_calls << ", num ways = " << num_ways << "\n";


return 0;
}

下面是一个 C # 函数:

    public static void change(int money, List<int> coins, List<int> combination)
{
if(money < 0 || coins.Count == 0) return;
if (money == 0)
{
Console.WriteLine((String.Join("; ", combination)));
return;
}


List<int> copy = new List<int>(coins);
copy.RemoveAt(0);
change(money, copy, combination);


combination = new List<int>(combination) { coins[0] };
change(money - coins[0], coins, new List<int>(combination));
}

Use it like this:

change(100, new List<int>() {5, 10, 25}, new List<int>());

它打印:

25; 25; 25; 25
10; 10; 10; 10; 10; 25; 25
10; 10; 10; 10; 10; 10; 10; 10; 10; 10
5; 10; 10; 25; 25; 25
5; 10; 10; 10; 10; 10; 10; 10; 25
5; 5; 10; 10; 10; 10; 25; 25
5; 5; 10; 10; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 10; 25; 25; 25
5; 5; 5; 10; 10; 10; 10; 10; 10; 25
5; 5; 5; 5; 10; 10; 10; 25; 25
5; 5; 5; 5; 10; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 25; 25; 25
5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 10; 10; 25; 25
5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 10; 25; 25
5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 25; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5

下面是一个查找所有货币组合的 Python 程序。这是一个带有订单(n)时间的动态编程解决方案。 Money is 1,5,10,25

我们从第1行转到第25行(4行)。如果我们只考虑1行中的钱，那么行中的钱1包含计数 calculating the number of combinations. Row money 5 produces each column by taking the count in row money r for the 相同的最后一笔钱加上前5个计数在自己的行(目前的位置减5)。排钱10用排钱5, which contains counts for both 1,5 and adds in the previous 10 count (current position minus 10). Row money 25 uses row 钱10，其中包含计数行钱1,5,10加上以前的25计数。

例如，数字[1][12] = 数字[0][12] + 数字[1][7](7 = 12-5)导致3 = 1 + 2; 数字[3][12] = 数字[2][12] + 数字[3][9](-13 = 12-25) ，结果是4 = 0 + 4，因为 -13小于0。

def cntMoney(num):
mSz = len(money)
numbers = [[0]*(1+num) for _ in range(mSz)]
for mI in range(mSz): numbers[mI][0] = 1
for mI,m in enumerate(money):
for i in range(1,num+1):
numbers[mI][i] = numbers[mI][i-m] if i >= m else 0
if mI != 0: numbers[mI][i] += numbers[mI-1][i]
print('m,numbers',m,numbers[mI])
return numbers[mSz-1][num]


money = [1,5,10,25]
num = 12
print('money,combinations',num,cntMoney(num))


output:
('m,numbers', 1, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
('m,numbers', 5, [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3])
('m,numbers', 10, [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4])
('m,numbers', 25, [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4])
('money,combinations', 12, 4)

以下 Mathematica中的一行程序将产生所需的结果

parts[n_]:=Flatten[Table[{(n-i)/25,(i-j)/10,(j-k)/5,k},{i,n,0,-25},{j,i,0,-10},{k,j,0,-5}],2]

这个表格通过迭代所有的方法来建立所有的组合，比如有多少个较大的硬币适合 n，同时对于其余的较小的硬币重复相同的步骤。在任何其他编程语言中，实现都应该是类似的琐碎。

输出是带有符号的元素列表:

{number of quarters, number of dimes, number of nickels, number of cents}

这种结构背后的直觉可以从一个例子中解读出来:

parts[51]

我在 C # 中实现了这个难题，我认为它与其他答案有些不同。此外，我添加了注释，使我的算法更容易理解。这是一个非常好的拼图。

从较大的硬币开始，看看所有的 Q,D,N和填补其余的硬币。

所以我可以从0/25开始，01角硬币和05分硬币，剩下的是1分硬币

对于每个硬币，我有 ($Amount / $Change) + 1，其中 $Amount 是输入参数，$Change 是[ Q ] uarter 或[ D ] ime 或[ N ] ickel。因此，假设输入参数是 $1,

• 我的代码中有($1/0.25) + 1 = 5个 Quarter (0,1,2,3,4)的选项—— qLoop变量
• 对于同样的 $1，我的代码中有($1/0.10) + 1 = 11个 Dime (0.1,2,3,4,5,6,7,8,9,10)的选项—— dLoop变量
• 对于 Nickel 也是一样，我的代码中有($1/0.05) + 1 = 21选项(0到20)—— nLoop变量

注意，在每个循环中，我必须使用来自外部循环的提醒。

例如，如果我选择1/4(q 为1) ，内部循环(Dime loop)的剩余值为1-0.25美元，以此类推

static void CoinCombination(decimal A)
{
decimal[] coins = new decimal[] { 0.25M, 0.10M, 0.05M, 0.01M };


// Loop for Quarters
int qLoop = (int)(A / coins[0]) + 1;
for (int q = 0; q < qLoop; q++)
{
string qS = $"{q} quarter(s), ";
decimal qAmount = A - (q * coins[0]);
Console.Write(qS);


// Loop for Dimes
int dLoop = (int)(qAmount / coins[1]) + 1;
for (int d = 0; d < dLoop; d++)
{
if (d > 0)
Console.Write(qS);
string dS = $"{d} dime(s), ";
decimal dAmount = qAmount - (d * coins[1]);
Console.Write(dS);


// Loop for Nickels
int nLoop = (int)(dAmount / coins[2]) + 1;
for (int n = 0; n < nLoop; n++)
{
if (n > 0)
Console.Write($"{qS}{dS}");
string nS = $"{n} nickel(s), ";
decimal nAmount = dAmount - (n * coins[2]);
Console.Write(nS);


// Fill up with pennies the remainder
int p = (int)(nAmount / coins[3]);
string pS = $"{p} penny(s)";
Console.Write(pS);


Console.WriteLine();
}
Console.WriteLine();
}
Console.WriteLine();
}
}

输出