当给定一些美元价值时如何find所有的硬币组合

我发现了几个月前我正在为面试准备的一段代码。

根据我的评论，它试图解决这个问题：

给定一些美分值（例如200 = 2美元，1000 = 10美元），找出组成美元值的所有硬币组合。 只有一分钱，镍，一angular和四分之一。 （季度= 25美分，一angular= 10美分，镍= 5美分，分钱= 1美分）

例如，如果有100个，答案应该是：

4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies 3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies etc. 

我相信这可以通过迭代和recursion的方式解决。 我的recursion解决scheme相当麻烦，我想知道其他人将如何解决这个问题。 这个问题的难点在于尽可能提高效率。

Answer 1

我很久以前就对这个问题进行了研究 ，你可以阅读我的小小的文字 。 这是Mathematica的源代码 。

通过使用生成函数，您可以获得问题的封闭forms的常量时间解决scheme。 Graham，Knuth和Patashnik的具体math就是这本书的一部分，对这个问题进行了相当广泛的讨论。 本质上，你定义了一个多项式，其中第n个系数是n元变化的方法数。

书面的第4-5页显示了如何使用Mathematica（或任何其他方便的计算机代数系统）在三行代码中几秒钟内计算出10 ^ 10 ^ 6美元的答案。

（而且这个时间足够长，在75Mhz的Pentium上这是几秒钟…）

Answer 2

清洁Scalafunction：

 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) 

Answer 3

我会赞成recursion解决scheme。 你有一些名单的面额，如果最小的一个可以均匀分割任何剩余的货币数量，这应该工作正常。

基本上，你从最大面额移动到最小面值。
recursion，

1. 你有一个目前的总数来填补，最大的面额（还剩1个以上）。 如果只剩下1个面额，只有一种方法来填补总额。 您可以使用您当前面额的0到k副本，使得k * cur面值<=总额。
2. 对于0到k，调用具有修改的总额和新的最大面额的函数。
3. 将结果从0增加到k。 这是多less种方式可以填补你目前面额下的总额。 返回这个数字。

这是我的python版本你陈述的问题，为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: comb.append( (left, denominations[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)) print count_combs(cents, 0, [], None) 

Answer 4

Scalafunction：

 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 } 

Answer 5

这里有一些非常简单的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; } 

但是我对于只计算组合数量的子问题颇感兴趣。 我怀疑它有一个封闭的等式。

Answer 6

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

 /* Q: Given some dollar value in cents (eg 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(nC[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(nC[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[iC[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; } 

Answer 7

半途破解独特的组合问题 – 强制降序：

  $ denoms = [1,5,10,25]
 def all_combs（sum，last） 
  如果sum == 0，则返回1
  返回$ denoms.select {| d |  d＆le sum && d＆le last} .inject（0）{| total，denom |
           总+ all_combs（和 -  DENOM，DENOM）}
结束

这将会运行缓慢，因为它不会被记忆，但你明白了。

Answer 8

代码是使用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)); } } 

Answer 9

设C（i，J）是使用集合J中的值使i美分的组合的集合。

您可以将C定义为：

（第一（J）以确定性的方式采取一组元素）

事实certificate，这是一个漂亮的recursion函数，如果使用记忆，效率也相当高;）

Answer 10

这是一个非常古老的问题，但是我想出了一个java中的recursion解决scheme，这个解决scheme似乎比所有其他解决scheme都小，所以在这里 –

  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,Ni*currdenom,vals); } } 

Answer 11

 # 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[jk]; return table[n]; } int main() { std::cout << count({25, 10, 5, 1}, 100) << std::endl; return 0; } 

Answer 12

这是我在Python中的答案。 它不使用recursion：

 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 

Answer 13

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

Answer 14

如果货币体系允许的话，一个简单的贪婪algorithm ，从最高价值货币开始，尽可能多地投入每一个硬币。

否则，需要dynamic编程来快速find最优解，因为这个问题本质上是背包问题 。

例如，如果一个货币系统有硬币： {13, 8, 1} ，贪婪的解决scheme将会改变为{13, 8, 1, 1, 1} ，但是真正的最优解是{8, 8, 8}

编辑：我认为我们正在做出最佳的变化，没有列出所有的方法来改变一美元。 我最近的一次采访问到如何做出改变，所以在完成阅读这个问题之前我跳了起来。

Answer 15

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

 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解决scheme，并使用recursion。

Answer 16

两者：遍历所有面额从高到低，取一个面额，从需求总量减去，然后recursion余数（约束avilable面额等于或低于当前的迭代值）。

Answer 17

杜，我现在觉得很愚蠢。 下面是一个过于复杂的解决scheme，我将保留，因为毕竟这是一个解决scheme。 一个简单的解决scheme是这样的：

 // 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" 

这是另一个解决scheme。 这个解决scheme是基于观察到每个硬币是其他的多个，所以他们可以用它们来表示。

 // 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 

Answer 18

这个我的博客条目解决了这个背包像XKCD漫画的人物问题。 对dict和exactcost值的一个简单的改变将产生你的问题的所有解决scheme。

如果问题是find使用最less成本的变化，那么使用尽可能多的最高价值硬币的天真的贪婪algorithm可能会失败一些硬币和目标数量的组合。 例如，如果有硬币值1,3和4; 并且目标数量是6，那么贪婪algorithm可能会build议三个值为4,1和1的硬币，当容易看到您可以使用两个值为3的硬币时。

• 稻田。

Answer 19

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

Answer 20

我在O'reily的书“Python For Data Analysis”中find了这一整段代码。 它使用懒惰的实现和int比较，我认为它可以修改为其他面额使用小数。 让我知道它是如何为你工作的！

 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 

Answer 21

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

Answer 22

这是紫汉答案的改进。 当面额只有1美分时，就会产生大量不必要的循环。

它直观而且不recursion。

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

Answer 23

Java解决scheme

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

}

Answer 24

下面的java解决scheme将打印不同的组合。 容易明白。 想法是

总和5

解决scheme是

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

}

Answer 25

这里是一个基于python的解决scheme，它使用recursion以及memoization导致复杂度为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 

Answer 26

下面是python解决scheme：

  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 

Answer 27

简单的java解决scheme：

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

Answer 28

PHP代码将金额细分为面值：

 //Define the denominations private $denominations = array(1000, 500, 200, 100, 50, 40, 20, 10, 5, 1); /** * S# countDenomination() function * * @author Edwin Mugendi <[e-mail]> * * 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＃countDenomination（）函数

Answer 29

这是一个简单的recursionalgorithm，它接受一个账单，然后recursion地取一个较小的账单，直到它达到总和，然后再取另一个相同面额的账单，并再次recursion。 请参阅下面的示例输出来进行说

 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 

Answer 30

这里有很多的变化，但无法find一个PHP解决scheme的组合数量的任何地方，所以我会添加一个。

 /** * @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);