如果给出一些美元价值,如何找到所有硬币组合

Question

几个月前,我找到了一段代码,我正在编写面试.

根据我的评论,它试图解决这个问题:

给定一美分的美分价值(例如200 = 2美元,1000 = 10美元),找到构成美元价值的所有硬币组合.只有便士(1¢),镍(5¢),角钱(10¢)和四分之一(25¢).

例如,如果给出100,答案应该是:

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

我相信这可以通过迭代和递归方式解决.我的递归解决方案非常错误,我想知道其他人如何解决这个问题.这个问题的难点在于尽可能提高效率.

Answer 1

我很久以前就研究了这个问题,你可以读一下我的小文章.这是Mathematica的来源.

通过使用生成函数,您可以获得问题的封闭形式的恒定时间解决方案.格雷厄姆,克努特和帕塔什尼克的混凝土数学就是这本书的书,并且对这个问题进行了相当广泛的讨论.基本上,您定义了一个多项式,其中第n个系数是以n美元进行更改的方式的数量.

这篇文章的第4-5页显示了如何使用Mathematica(或任何其他方便的计算机代数系统)在三行代码中在几秒钟内计算10 ^ 10 ^ 6美元的答案.

(而且这已经很久以前在75Mhz Pentium上只有几秒钟......)

Answer 2

注意:这仅显示方式的数量.

Scala功能:

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

我赞成递归解决方案.你有一些面额列表,如果最小的面额可以平均分配任何剩余的货币金额,这应该工作正常.

基本上,您从最大面额移动到最小面额.
递归,

1. 您有一个当前总数要填充,以及一个最大面额(剩下超过1个).如果只剩下1个面额,那么只有一种方法可以填补总数.您可以使用当前面额的0到k个副本,使得k*cur面额<=总计.
2. 对于0到k,使用修改的总计和新的最大面额调用函数.
3. 将结果从0添加到k.这就是你可以用多少种方式从目前的面额中填补总数.返回此号码.

这是我所说的问题的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:
           if left % denominations[i]:
               return 0
           comb.append( (left/denominations[i], demoninations[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))

count_combs(cents, 0, [], None)

Answer 4

Scala功能:

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

子问题是典型的动态规划问题.

/* Q: Given some dollar value in cents (e.g. 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(n-C[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(n-C[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[i-C[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

这是一个非常古老的问题,但我想出了一个java中的递归解决方案,似乎比其他所有解决方案都小,所以这里 -

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

改进:

  public static void printAllCents(int ind, int[] denom,int N,int[] vals){
        if(N==0){
            if(ind < denom.length) {
                for(int i=ind;i<denom.length;i++)
                    vals[i] = 0;
            }
            System.out.println(Arrays.toString(vals));
            return;
        }
        if(ind == (denom.length)) {
            vals[ind-1] = 0;
            return;             
        }

        int currdenom = denom[ind];
        for(int i=0;i<=(N/currdenom);i++){ 
                vals[ind] = i;
                printAllCents(ind+1,denom,N-i*currdenom,vals);
        }
     }

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定义为:

(first(J)以确定的方式获取集合的元素)

它结果是一个非常递归的函数...如果你使用memoization,效率相当;)

Answer 10

半黑客绕过独特的组合问题 - 强制降序:

$denoms = [1,5,10,25]
def all_combs(sum,last) 
  return 1 if sum == 0
  return $denoms.select{|d| d &le sum && d &le last}.inject(0) {|total,denom|
           total+all_combs(sum-denom,denom)}
end

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

Answer 11

两者：从高到低迭代所有面额，取其中一种面额，从所需总数中减去，然后对余数进行递归（将可用面额限制为等于或低于当前迭代值。）