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

Question

我正在尝试实现一个硬币问题，问题规范如下

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

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[])

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

有人指导我如何实现这个吗？

Answer 1

使用递归。

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 2

尽管递归可以发挥作用，并且通常是一些大学水平的算法和递归课程中需要实施的作业。数据结构，我相信“动态编程”实现效率更高。

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 3

您可以使用生成函数方法来给出使用复数的快速算法。

给定硬币值 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) + ...)

中查找 x^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 系数：

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

计算机程序应该能够轻松找到 Ai 和 ai （可以是复数）。当然，这可能涉及浮点计算。

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

希望有帮助。

Answer 4

递归非常简单：

 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

Aryabhatta 的回答
计算用固定的硬币找零的方式的数量
面额很可爱，但实施起来也不切实际
描述的。我们将使用模块化，而不是使用复数
算术，类似于数论变换如何替换
用于乘以整数多项式的傅里叶变换。

令D 为硬币面额的最小公倍数。经过
狄利克雷算术级数定理，存在无限
许多质数 p 使得 D 整除 p - 1。 （如果运气好的话，
它们甚至会以我们可以找到它们的方式分发
有效地。）我们将计算对某些 p 取模的方式数
满足这个条件。通过以某种方式获得粗略的界限（例如，
n + k - 1 选择 k - 1，其中 n 是总数，k 是数字
的面额），用几个不同的重复此过程
乘积超过该界限的素数，并应用中文
余数定理，我们可以恢复出精确的数。

测试候选者 1 + k*D 是否为整数 k > 0 直到我们找到素数
p。令g为原根模p（生成候选
随机并应用标准测试）。对于每个面额 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)。下一步是找到一个
部分分数分解 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 如果面额为奇数。推导出一个系统
通过计算给定两边的值来得到 A(j) 的线性方程
不同x值的方程，然后用高斯求解
消除。如果存在重复，生活就会变得复杂；选择另一个素数可能是最简单的。

给定这个设置，我们可以计算路数（模p，
当然）进行总计 n 的更改为

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

Answer 6

提到的递归解决方案是可行的，但如果您添加更多硬币面额和/或显着增加目标值，它们将会非常慢。

您需要加快速度的是实现动态编程解决方案。查看背包问题。您可以采用那里提到的 DP 解决方案来解决您的问题，方法是记录可以达到总数的方式数量，而不是所需的最小硬币数量。

Answer 7

package algorithms;

import java.util.Random;

/**`enter code here`
 * Owner : Ghodrat Naderi
 * E-Mail: [email protected]
 * 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 8

递归解决方案可能是正确的答案：

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

警告：我还没有测试甚至编译上面的内容。

Answer 9

@Jordi 提供的解决方案很好，但运行速度非常慢。您可以尝试在该解决方案中输入 600 并查看它有多慢。

我的想法是使用自下而上的动态规划。

请注意，一般来说，money=m 和 coin{a,b,c} 的可能组合等于

• mc 和 coin{a,b,c}（有 coin c）
• 的组合（没有 coin c）m 和 coin{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

该代码基于 JeremyP 提供的解决方案，该解决方案工作完美，我只是通过使用动态编程对其进行了增强以优化性能。我无法对 JeremyP 帖子发表评论，因为我没有足够的声誉:)

public static long makeChange(int[] coins, int money) {
    Long[][] resultMap = new Long[coins.length][money+1];
    return getChange(coins,money,0,resultMap);
}

public static long getChange(int[] coins, int money, int index,Long[][] resultMap) {
    if (index == coins.length -1) // if we are at the end      
        return money%coins[index]==0? 1:0;
    else{
        //System.out.printf("Checking index %d and money %d ",index,money);
        Long storedResult =resultMap[index][money];
        if(storedResult != null)
            return storedResult;
        long total=0;
        for(int coff=0; coff * coins[index] <=money; coff ++){

             total += getChange(coins, money - coff*coins[index],index +1,resultMap);
        }
        resultMap[index][money] = total;
        return total;

    }
}

Answer 11

第一个想法：（

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

在这种情况下“<=”是多余的，但如果您决定更改参数，则需要更通用的解决方案）

Answer 12

下面是带有记忆化java解决方案的递归。对于下面的一个，我们有 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

#include<iostream>
using namespace std;

int solns = 0;

void countComb(int* arr, int low, int high, int Val)
{
    bool b = false;
    for (size_t i = low; i <= high; i++)
    {
        if (Val - arr[i] == 0)
        {
            solns++;
            break;
        }
        else if (Val - arr[i] > 0)
            countComb(arr, i, high, Val - arr[i]);
        
    }
}

int main()
{
    int coins[] = { 1,2,5 };
    int value = 7;
    int arrSize = sizeof(coins) / sizeof(int);
    countComb(coins,0, arrSize,value);
    cout << solns << endl;
    return 0;
}

Answer 14

再次使用递归作为经过测试的解决方案，尽管可能不是最优雅的代码。 （请注意，它返回要使用的每种硬币的数量，而不是重复实际的硬币数量 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 15

动态规划解决方案

给定一系列面额D = {d1, d2, d3, ... , dm} 和目标金额W。请注意，D 不需要排序。

令 T(i, j) 为仅使用第 i 左边的面额组成金额 j 的组合数量（可以包含自身）在 D 中。

我们有：

• T(0, 0) = 1：由于金额为 0，因此只有 1 个有效组合可以组成 0 code>，这是空集。

• T(i, j) = T(i - 1, j) 如果 D[i] > j

• T(i, j) = T(i - 1, j) + T(i, j - D[i]) if D[i] <= j

   public int change(int amount, int[] coin) {
        int m = 硬币. 长度;
        int n = 金额；
  
        int[][] dp = 新 int[m + 1][n + 1];
  
        dp[0][0] = 1;
  
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (j < 硬币[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                }
                别的 {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 硬币[i - 1]];
                }
            }
        }
  
        返回dp[m][n]；
    }
  

Answer 16

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 17

下面是我创建的递归回溯解决方案，它列出并计算了所有可能的面额（硬币）组合，总计达到给定金额。

面额和金额都可以是动态的

public class CoinComboGenerate {  
      public static final int[] DENO = {1,6,7};
      public static final int AMOUNT = 15;
      public static int count = 0;
    
      public static void change(int amount) {
        change(amount, new ArrayList<>(),0);  
      }
    
      private static void change(int rem, List<Integer> coins, int pos) {    
        if (rem == 0) {
          count++;
          System.out.println(count+")"+coins);
          return;
        }
        
        while(pos<DENO.length){            
          if (rem >= DENO[pos]) {
            coins.add(DENO[pos]);
            change(rem - DENO[pos], coins,pos);
            coins.remove(coins.size() - 1);  //backtrack
          }
          pos++;
        }  
      }
    
      public static void main(String[] args) {
            change(AMOUNT);
      }   
    }

输出：
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]

Answer 18

对于硬币（1,5,10,25,50）的相同问题有以下解决方案之一。
解应满足以下方程：
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);
                            }
                        }
                    }
                }
            }
        }
    }

这可以针对任何通用解决方案进行修改。