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

How to count possible combination for coin problem

提问by Preetam Purbia

I am trying to implement a coin problem, Problem specification is like this

我正在尝试实现一个硬币问题，问题规范是这样的

Create a function to count all possible combination of coins which can be used for given amount.

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

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,

function prototype:

函数原型：

int findCombinationsCount(int amount, int coins[])

assume that coin array is sorted. for above example this function should return 6.

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

Anyone guide me how to implement this??

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

采纳答案by aronp

You can use generating function methods to give fast algorithms, which use complex numbers.

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

Given the coin values c1, c2, .., ck, to get the number of ways to sum n, what you need is the coefficient of x^n in

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

Which is the same as finding the coefficient of x^n in

这与在中找到 x^n 的系数相同

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

Now using complex numbers, x^a - 1 = (x-w1)(x-w2)...(x-wa) where w1, w2 etc are the complex roots of unity.

现在使用复数，x^a - 1 = (x-w1)(x-w2)...(x-wa) 其中 w1、w2 等是复数单位根。

So

所以

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

can be written as

可以写成

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

which can be rewritten using partial fractions are

可以使用部分分数重写的是

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

The coefficient of x^n in this can be easily found:

可以很容易地找到 x^n 的系数：

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

A computer program should easily be able to find Ai and ai (which could be complex numbers). Of course, this might involve floating point computations.

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

For large n, this will be probably faster than enumerating all the possible combinations.

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

Hope that helps.

希望有帮助。

回答by Jordi

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

You should check this implementation though. I don't have a Java IDE here, and I'm a little rusty, so it may have some errors.

不过，您应该检查此实现。我这里没有Java IDE，我有点生疏，所以它可能有一些错误。

回答by JeremyP

A recursive solution might be the right answer here:

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

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

Warning: I haven't tested or even compiled the above.

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

回答by G B

First idea:

第一个想法：

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

(the '<=' is superfluous in this case, but is needed for a more general solution, if you decide to change your parameters)

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

回答by moinudin

The recursive solutions mentioned will work, but they're going to be horrendously slow if you add more coin denominations and/or increase the target value significantly.

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

What you need to speed it up is to implement a dynamic programming solution. Have a look at the knapsack problem. You can adapt the DP solution mentioned there to solve your problem by keeping a count of the number of ways a total can be reached rather than the minimum number of coins required.

您需要加快速度的是实现动态编程解决方案。看看背包问题。您可以调整那里提到的 DP 解决方案来解决您的问题，方法是计算可以达到的总数，而不是所需的最少硬币数量。

回答by aronp

Again using recursion a tested solution, though probably not the most elegant code. (note it returns the number of each coin to use rather than repeating the actual coin ammount n times).

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

}

}

回答by cyberkid

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

回答by Domenic D.

Although recursion can work and is often an assignment to implement in some college level courses on Algorithms & Data Structures, I believe the "dynamic programming" implementation is more efficient.

虽然递归可以工作并且通常是在一些大学水平的算法和数据结构课程中实现的任务，但我相信“动态编程”实现更有效。

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

回答by Ghodrat Naderi

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

回答by user1701576

The same problem for coins(1,5,10,25,50) has one of below solutions. The solution should satisfy below equation: 1*a + 5*b + 10*c + 25*d + 50*e == cents

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

public static void countWaysToProduceGivenAmountOfMoney(int 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);
                        }
                    }
                }
            }
        }
    }
}

This can be modified for any general solutions.

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