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

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

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

这与在

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).

计算机程序应该很容易找到人工智能和人工智能(可能是复数)。当然,这可能涉及浮点计算。

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

希望能有所帮助。

使用递归。

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

不过,您应该检查这个实现。我这里没有JavaIDE,而且我有点生疏,所以它可能有一些错误。

尽管递归可以工作,而且在一些大学级的算法和数据结构课程中经常是一项要实现的任务,但我相信“动态编程”的实现更有效。

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

递归非常简单:

 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中的示例

Aryabhatta’s answer 对于 计算使用固定硬币进行改变的方法的数量 面额非常可爱,但也不切实际 描述。我们将使用模块化而不是复数 算术,类似于数论变换如何代替 整数多项式乘法的傅里叶变换。

让 D 是硬币面额中最不常见的倍数。由 算术级数的Dirichletγ定理无限存在 许多素数 p 如此 丁 分歧 p - 1 . (运气好的话, 它们的分布方式甚至可以让我们找到它们 有效地)我们将计算一些 第页 满足这个条件。通过某种方式获得一个粗糙的边界(例如。, n + k - 1 选择 k - 1 哪里 n 是总数和 k 是号码 ,用几个不同的 乘积超过这个界限的素数,及其在汉语中的应用 余数定理,我们可以得到精确的数。

应试者 1 + k*D 对于整数 k > 0 直到我们找到一个质数 第页 g 是一个原始根模 第页 (在以下位置生成候选人 随机选择并应用标准测试)。每种面值 d ,快车 多项式 x**d - 1 模 第页

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

请注意 丁 分歧 丁 分歧 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 ,然后用高斯函数求解 消除。如果有重复的话,生活会变得复杂;选择另一个质数可能是最容易的。

给定这个设置,我们可以计算 第页 ,共 课程)做出相当于 n个 作为

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

package algorithms;

import java.util.Random;

/**`enter code here`
 * Owner : Ghodrat Naderi
 * E-Mail: Naderi.ghodrat@gmail.com
 * 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;
   }
 }

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

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

警告:我还没有测试,甚至没有编译以上内容。

上面提到的递归解决方案会起作用,但是如果你增加更多的硬币面额和/或显著增加目标值,它们的速度会非常慢。

您需要加速的是实现一个动态编程解决方案。看看 knapsack problem . 您可以调整这里提到的DP解决方案来解决您的问题,方法是记下达到总数的方法数,而不是所需的最小硬币数。

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

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

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

• m-c和硬币{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]);

}

这段代码基于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;

    }
}

第一个想法:

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

(在这种情况下,“<=”是多余的,但如果您决定更改参数,则需要更一般的解决方案)

再次使用递归是一个经过测试的解决方案,虽然可能不是最优雅的代码。(注意,它返回要使用的每个硬币的编号,而不是重复实际的硬币弹药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);
    }
}

}

下面是使用memoization 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;
}

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

硬币(1,5,10,25,50)的相同问题有以下解决方案之一。 解应满足下列方程: 1*a+5*b+10*c+25*d+50*e==美分

公共静态void countWaysToProduceGivenAmountOfMoney(整数分){

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

对于任何一般解决方案,都可以对其进行修改。