如何计算硬币问题的可能组合

我正在试图实现一个硬币的问题，问题说明是这样的

创build一个函数来计算可用于给定数量的所有可能的硬币组合。

All possible combinations for given amount=15, coin types=1 6 7 1) 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 2) 1,1,1,1,1,1,1,1,1,6, 3) 1,1,1,1,1,1,1,1,7, 4) 1,1,1,6,6, 5) 1,1,6,7, 6) 1,7,7, 

函数原型：

 int findCombinationsCount(int amount, int coins[]) 

假设硬币数组是sorting的。 对于上面的例子，这个函数应该返回6。

任何人指导我如何实现这？

Answer 1

您可以使用生成函数方法来提供使用复数的快速algorithm。

给定硬币值c1，c2，…，ck，得到总和n的方法数，你需要的是x ^ n的系数

 (1 + x^c1 + x^(2c1) + x^(3c1) + ...)(1+x^c2 + x^(2c2) + x^(3c2) + ...)....(1+x^ck + x^(2ck) + x^(3ck) + ...) 

这和findx ^ n的系数是一样的

 1/(1-x^c1) * 1/(1-x^c2) * ... * (1-x^ck) 

现在使用复数，x ^ a-1 =（x-w1）（x-w2）…（x-wa）其中w1，w2等是统一的复数根。

所以

 1/(1-x^c1) * 1/(1-x^c2) * ... * (1-x^ck) 

可以写成

 1/(x-a1)(x-a2)....(x-am) 

可以使用部分分数重写

 A1/(x-a1) + A2/(x-a2) + ... + Am/(x-am) 

在这个x ^ n的系数可以很容易地find：

 A1/(a1)^(n+1) + A2/(a2)^(n+1) + ...+ Am/(am)^(n+1). 

一个计算机程序应该很容易findAi和ai（可能是复数）。 当然，这可能涉及浮点计算。

对于大n，这可能比列举所有可能的组合更快。

希望有所帮助。

Answer 2

使用recursion。

 int findCombinationsCount(int amount, int coins[]) { return findCombinationsCount(amount, coins, 0); } int findCombinationsCount(int amount, int coins[], int checkFromIndex) { if (amount == 0) return 1; else if (amount < 0 || coins.length == checkFromIndex) return 0; else { int withFirstCoin = findCombinationsCount(amount-coins[checkFromIndex], coins, checkFromIndex); int withoutFirstCoin = findCombinationsCount(amount, coins, checkFromIndex+1); return withFirstCoin + withoutFirstCoin; } } 

你应该检查这个实现。 我在这里没有Java IDE，而且我有点生疏，所以可能会有一些错误。

Answer 3

虽然recursion可以工作，而且往往是在一些大学水平的algorithm和数据结构课程实施，我相信“dynamic规划”实施更有效率。

 public static int findCombinationsCount(int sum, int vals[]) { if (sum < 0) { return 0; } if (vals == null || vals.length == 0) { return 0; } int dp[] = new int[sum + 1]; dp[0] = 1; for (int i = 0; i < vals.length; ++i) { for (int j = vals[i]; j <= sum; ++j) { dp[j] += dp[j - vals[i]]; } } return dp[sum]; } 

Answer 4

recursion非常简单：

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

这是SCALA的例子

Answer 5

 package algorithms; import java.util.Random; /**`enter code here` * Owner : Ghodrat Naderi * E-Mail: [e-mail] * Date : 10/12/12 * Time : 4:50 PM * IDE : IntelliJ IDEA 11 */ public class CoinProblem { public static void main(String[] args) { int[] coins = {1, 3, 5, 10, 20, 50, 100, 200, 500}; int amount = new Random().nextInt(10000); int coinsCount = 0; System.out.println("amount = " + amount); int[] numberOfCoins = findNumberOfCoins(coins, amount); for (int i = 0; i < numberOfCoins.length; i++) { if (numberOfCoins[i] > 0) { System.out.println("coins= " + coins[i] + " Count=" + numberOfCoins[i] + "\n"); coinsCount += numberOfCoins[i]; } } System.out.println("numberOfCoins = " + coinsCount); } private static int[] findNumberOfCoins(int[] coins, int amount) { int c = coins.length; int[] numberOfCoins = new int[coins.length]; while (amount > 0) { c--; if (amount >= coins[c]) { int quotient = amount / coins[c]; amount = amount - coins[c] * quotient; numberOfCoins[c] = quotient; } } return numberOfCoins; } } 

Answer 6

Aryabhatta的答案是用固定面额的硬币来计算改变方式的数量是非常可爱的，但是如所描述的那样实施也是不切实际的。 我们将使用模运算，而不是使用复数，这与数乘理论变换取代用于乘整数多项式的傅立叶变换相似。

D是硬币面值的最小公倍数。 根据狄利克雷（Dirichlet）关于算术级数的定理，存在无限多的素数p ，使得D除以p - 1 。 （如果运气好的话，它们甚至会以一种可以高效地find它们的方式进行分配）。我们将计算满足这种条件的模的数量。 通过某种方式获得一个粗略的界限（例如， n + k - 1selectk - 1 ，其中n是总数， k是面额数），用产品超出界限的几个不同的素数重复这个过程，定理，我们可以恢复确切的数字。

testing候选人1 + k*D的整数k > 0直到find一个素数p 。 令g为原始根模p （随机生成候选项并应用标准testing）。 对于每个面额d ，表示多项式x**d - 1模p作为因子的乘积：

 x**d - 1 = product from i=0 to d-1 of (x - g**((p-1)*i/d)) [modulo p]. 

请注意， d除D分p-1 ，所以指数确实是一个整数。

设m是面额的总和。 收集所有常数g**((p-1)*i/d)作为a(0), ..., a(m-1) 。 下一步是find一个部分分解分解A(0), ..., A(m-1)

 sign / product from j=0 to m-1 of (a(j) - x) = sum from j=0 to m-1 of A(j)/(a(j) - x) [modulo p], 

如果有偶数个面值，则sign为1如果有奇数个面额，则为-1 。 通过对给定方程的两边求x不同值，导出A(j)的线性方程组，然后用高斯消元法求解。 如果有重复，生活变得复杂; 只是select另一个素数可能是最简单的。

给定这个设置，我们可以计算方法的数量（当然是模p ），使得改变等于n

 sum from j=0 to m-1 of A(j) * (1/a(j))**(n+1). 

Answer 7

recursion解决scheme在这里可能是正确的答案：

 int findCombinationsCount(int amount, int coins[]) { // I am assuming amount >= 0, coins.length > 0 and all elements of coins > 0. if (coins.length == 1) { return amount % coins[0] == 0 ? 1 : 0; } else { int total = 0; int[] subCoins = arrayOfCoinsExceptTheFirstOne(coins); for (int i = 0 ; i * coins[0] <= amount ; ++i) { total += findCombinationsCount(amount - i * coins[0], subCoins); } return total; } } 

警告：我还没有testing甚至编译上述。

Answer 8

所提到的recursion解决scheme将起作用，但如果您添加更多硬币面额和/或显着增加目标值，它们将会非常慢。

你需要加速的是实现一个dynamic编程解决scheme。 看看背包问题 。 您可以调整DP解决scheme来解决您的问题，方法是保持总数可以达到的数量，而不是所需的最小硬币数量。

Answer 9

@Jordi提供的解决scheme很好，但运行速度非常慢。 您可以尝试input600到该解决scheme，看看它是多么慢。

我的想法是使用自下而上的dynamic编程。

请注意，一般来说，货币= m和硬币{a，b，c}的可能组合等于组合

• mc和硬币{a，b，c}（用硬币c）
• m和硬币{a，b}（没有硬币c）的组合。

如果没有可用的硬币或可用的硬币不能满足所需的金额，则应相应地填入0。 如果金额为0，则应填入1。

 public static void main(String[] args){ int[] coins = new int[]{1,2,3,4,5}; int money = 600; int[][] recorder = new int[money+1][coins.length]; for(int k=0;k<coins.length;k++){ recorder[0][k] = 1; } for(int i=1;i<=money;i++){ //System.out.println("working on money="+i); int with = 0; int without = 0; for(int coin_index=0;coin_index<coins.length;coin_index++){ //System.out.println("working on coin until "+coins[coin_index]); if(i-coins[coin_index]<0){ with = 0; }else{ with = recorder[i-coins[coin_index]][coin_index]; } //System.out.println("with="+with); if(coin_index-1<0){ without = 0; }else{ without = recorder[i][coin_index-1]; } //System.out.println("without="+without); //System.out.println("result="+(without+with)); recorder[i][coin_index] = with+without; } } System.out.print(recorder[money][coins.length-1]); } 

Answer 10

第一个想法：

 int combinations = 0; for (int i = 0; i * 7 <=15; i++) { for (int j = 0; j * 6 + i * 7 <= 15; j++) { combinations++; } } 

（在这种情况下，“<=”是多余的，但如果您决定更改参数，则需要更一般的解决scheme）

Answer 11

再次使用recursiontesting的解决scheme，虽然可能不是最优雅的代码。 （注意它返回使用的每个硬币的数量，而不是重复n次的实际硬币）。

 public class CoinPerm { @Test public void QuickTest() throws Exception { int ammount = 15; int coins[] = {1,6,7}; ArrayList<solution> solutionList = SolvePerms(ammount, coins); for (solution sol : solutionList) { System.out.println(sol); } assertTrue("Wrong number of solutions " + solutionList.size(),solutionList.size() == 6); } public ArrayList<solution> SolvePerms(int ammount, int coins[]) throws Exception { ArrayList<solution> solutionList = new ArrayList<solution>(); ArrayList<Integer> emptyList = new ArrayList<Integer>(); solution CurrentSolution = new solution(emptyList); GetPerms(ammount, coins, CurrentSolution, solutionList); return solutionList; } private void GetPerms(int ammount, int coins[], solution CurrentSolution, ArrayList<solution> mSolutions) throws Exception { int currentCoin = coins[0]; if (currentCoin <= 0) { throw new Exception("Cant cope with negative or zero ammounts"); } if (coins.length == 1) { if (ammount % currentCoin == 0) { CurrentSolution.add(ammount/currentCoin); mSolutions.add(CurrentSolution); } return; } // work out list with one less coin. int coinsDepth = coins.length; int reducedCoins[] = new int[(coinsDepth -1 )]; for (int j = 0; j < coinsDepth - 1;j++) { reducedCoins[j] = coins[j+1]; } // integer rounding okay; int numberOfPerms = ammount / currentCoin; for (int j = 0; j <= numberOfPerms; j++) { solution newSolution = CurrentSolution.clone(); newSolution.add(j); GetPerms(ammount - j * currentCoin,reducedCoins, newSolution, mSolutions ); } } private class solution { ArrayList<Integer> mNumberOfCoins; solution(ArrayList<Integer> anumberOfCoins) { mNumberOfCoins = anumberOfCoins; } @Override public String toString() { if (mNumberOfCoins != null && mNumberOfCoins.size() > 0) { String retval = mNumberOfCoins.get(0).toString(); for (int i = 1; i< mNumberOfCoins.size();i++) { retval += ","+mNumberOfCoins.get(i).toString(); } return retval; } else { return ""; } } @Override protected solution clone() { return new solution((ArrayList<Integer>) mNumberOfCoins.clone()); } public void add(int i) { mNumberOfCoins.add(i); } } 

}

Answer 12

下面是memoization java解决scheme的recursion。 下面我们有1,2,3,5作为硬币和200作为目标金额。

 countCombinations(200,new int[]{5,2,3,1} , 0, 0,new Integer[6][200+5]); static int countCombinations(Integer targetAmount, int[] V,int currentAmount, int coin, Integer[][] memory){ //Comment below if block if you want to see the perf difference if(memory[coin][currentAmount] != null){ return memory[coin][currentAmount]; } if(currentAmount > targetAmount){ memory[coin][currentAmount] = 0; return 0; } if(currentAmount == targetAmount){ return 1; } int count = 0; for(int selectedCoin : V){ if(selectedCoin >= coin){ count += countCombinations(targetAmount, V, currentAmount+selectedCoin, selectedCoin,memory); } } memory[coin][currentAmount] = count; return count; } 

Answer 13

 public static void main(String[] args) { int b,c,total = 15; int combos =1; for(int d=0;d<total/7;d++) { b = total - d * 7; for (int n = 0; n <= b /6; n++) { combos++; } } System.out.print("TOTAL COMBINATIONS = "+combos); } 

Answer 14

硬币（1,5,10,25,50）的相同问题有以下解决scheme之一。 该解应该满足以下等式：1 * a + 5 * b + 10 * c + 25 * d + 50 * e == cents

public static void countWaysToProduceGivenAmountOfMoney（int cents）{

  for(int a = 0;a<=cents;a++){ for(int b = 0;b<=cents/5;b++){ for(int c = 0;c<=cents/10;c++){ for(int d = 0;d<=cents/25;d++){ for(int e = 0;e<=cents/50;e++){ if(1*a + 5*b + 10*c + 25*d + 50*e == cents){ System.out.println("1 cents :"+a+", 5 cents:"+b+", 10 cents:"+c); } } } } } } } 

这可以修改任何一般的解决scheme。