Как найти все комбинации монет, когда дано какое-то долларовое значение

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

Вот функция C #:

    public static void change(int money, List<int> coins, List<int> combination)
    {
        if(money < 0 || coins.Count == 0) return;
        if (money == 0)
        {
            Console.WriteLine((String.Join("; ", combination)));
            return;
        }

        List<int> copy = new List<int>(coins);
        copy.RemoveAt(0);
        change(money, copy, combination);

        combination = new List<int>(combination) { coins[0] };
        change(money - coins[0], coins, new List<int>(combination));
    }

Используйте это так:

change(100, new List<int>() {5, 10, 25}, new List<int>());

Он печатает:

25; 25; 25; 25
10; 10; 10; 10; 10; 25; 25
10; 10; 10; 10; 10; 10; 10; 10; 10; 10
5; 10; 10; 25; 25; 25
5; 10; 10; 10; 10; 10; 10; 10; 25
5; 5; 10; 10; 10; 10; 25; 25
5; 5; 10; 10; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 10; 25; 25; 25
5; 5; 5; 10; 10; 10; 10; 10; 10; 25
5; 5; 5; 5; 10; 10; 10; 25; 25
5; 5; 5; 5; 10; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 25; 25; 25
5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 10; 10; 25; 25
5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 10; 25; 25
5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 25; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5

Answer 2

/*
* make a list of all distinct sets of coins of from the set of coins to
* sum up to the given target amount.
* Here the input set of coins is assumed yo be {1, 2, 4}, this set MUST
* have the coins sorted in ascending order.
* Outline of the algorithm:
* 
* Keep track of what the current coin is, say ccn; current number of coins
* in the partial solution, say k; current sum, say sum, obtained by adding
* ccn; sum sofar, say accsum:
*  1) Use ccn as long as it can be added without exceeding the target
*     a) if current sum equals target, add cc to solution coin set, increase
*     coin coin in the solution by 1, and print it and return
*     b) if current sum exceeds target, ccn can't be in the solution, so
*        return
*     c) if neither of the above, add current coin to partial solution,
*        increase k by 1 (number of coins in partial solution), and recuse
*  2) When current denomination can no longer be used, start using the
*     next higher denomination coins, just like in (1)
*  3) When all denominations have been used, we are done
*/

#include <iostream>
#include <cstdlib>

using namespace std;

// int num_calls = 0;
// int num_ways = 0;

void print(const int coins[], int n);

void combine_coins(
                   const int denoms[], // coins sorted in ascending order
                   int n,              // number of denominations
                   int target,         // target sum
                   int accsum,         // accumulated sum
                   int coins[],        // solution set, MUST equal
                                       // target / lowest denom coin
                   int k               // number of coins in coins[]
                  )
{

    int  ccn;   // current coin
    int  sum;   // current sum

    // ++num_calls;

    for (int i = 0; i < n; ++i) {
        /*
         * skip coins of lesser denomination: This is to be efficient
         * and also avoid generating duplicate sequences. What we need
         * is combinations and without this check we will generate
         * permutations.
         */
        if (k > 0 && denoms[i] < coins[k - 1])
            continue;   // skip coins of lesser denomination

        ccn = denoms[i];

        if ((sum = accsum + ccn) > target)
            return;     // no point trying higher denominations now


        if (sum == target) {
            // found yet another solution
            coins[k] = ccn;
            print(coins, k + 1);
            // ++num_ways;
            return;
        }

        coins[k] = ccn;
        combine_coins(denoms, n, target, sum, coins, k + 1);
    }
}

void print(const int coins[], int n)
{
    int s = 0;
    for (int i = 0; i < n; ++i) {
        cout << coins[i] << " ";
        s += coins[i];
    }
    cout << "\t = \t" << s << "\n";

}

int main(int argc, const char *argv[])
{

    int denoms[] = {1, 2, 4};
    int dsize = sizeof(denoms) / sizeof(denoms[0]);
    int target;

    if (argv[1])
        target = atoi(argv[1]);
    else
        target = 8;

    int *coins = new int[target];


    combine_coins(denoms, dsize, target, 0, coins, 0);

    // cout << "num calls = " << num_calls << ", num ways = " << num_ways << "\n";

    return 0;
}

Answer 3

public class Coins {

static int ac = 421;
static int bc = 311;
static int cc = 11;

static int target = 4000;

public static void main(String[] args) {


    method2();
}

  public static void method2(){
    //running time n^2

    int da = target/ac;
    int db = target/bc;     

    for(int i=0;i<=da;i++){         
        for(int j=0;j<=db;j++){             
            int rem = target-(i*ac+j*bc);               
            if(rem < 0){                    
                break;                  
            }else{                  
                if(rem%cc==0){                  
                    System.out.format("\n%d, %d, %d ---- %d + %d + %d = %d \n", i, j, rem/cc, i*ac, j*bc, (rem/cc)*cc, target);                     
                }                   
            }                   
        }           
    }       
}
 }

Answer 4

Это простой рекурсивный алгоритм, который принимает счет, затем рекурсивно принимает меньший счет, пока не достигнет суммы, затем принимает другой счет того же номинала и рекурсивно повторяется. См. Пример выходных данных ниже для иллюстрации.

var bills = new int[] { 100, 50, 20, 10, 5, 1 };

void PrintAllWaysToMakeChange(int sumSoFar, int minBill, string changeSoFar)
{
    for (int i = minBill; i < bills.Length; i++)
    {
        var change = changeSoFar;
        var sum = sumSoFar;

        while (sum > 0)
        {
            if (!string.IsNullOrEmpty(change)) change += " + ";
            change += bills[i];

            sum -= bills[i]; 
            if (sum > 0)
            {
                PrintAllWaysToMakeChange(sum, i + 1, change);
            }
        }

        if (sum == 0)
        {
            Console.WriteLine(change);
        }
    }
}

PrintAllWaysToMakeChange(15, 0, "");

Печатает следующее:

10 + 5
10 + 1 + 1 + 1 + 1 + 1
5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
5 + 5 + 1 + 1 + 1 + 1 + 1
5 + 5 + 5
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Answer 5

Простое решение Java:

public static void main(String[] args) 
{    
    int[] denoms = {4,2,3,1};
    int[] vals = new int[denoms.length];
    int target = 6;
    printCombinations(0, denoms, target, vals);
}


public static void printCombinations(int index, int[] denom,int target, int[] vals)
{
  if(target==0)
  {
    System.out.println(Arrays.toString(vals));
    return;
  }
  if(index == denom.length) return;   
  int currDenom = denom[index];
  for(int i = 0; i*currDenom <= target;i++)
  {
    vals[index] = i;
    printCombinations(index+1, denom, target - i*currDenom, vals);
    vals[index] = 0;
  }
}

Answer 6

Это улучшение ответа Зихана. Большое количество ненужных петель возникает, когда деноминация составляет всего 1 цент.

Интуитивно понятный и нерекурсивный.

    public static int Ways2PayNCents(int n)
    {
        int numberOfWays=0;
        int cent, nickel, dime, quarter;
        for (quarter = 0; quarter <= n/25; quarter++)
        {
            for (dime = 0; dime <= n/10; dime++)
            {
                for (nickel = 0; nickel <= n/5; nickel++)
                {
                    cent = n - (quarter * 25 + dime * 10 + nickel * 5);
                    if (cent >= 0)
                    {
                        numberOfWays += 1;
                        Console.WriteLine("{0},{1},{2},{3}", quarter, dime, nickel, cent);
                    }                   
                }
            }
        }
        return numberOfWays;            
    }

Answer 7

Здесь много вариантов, но нигде не удалось найти PHP-решение для количества комбинаций, поэтому я добавлю одно.

/**
 * @param int $money The total value
 * @param array $coins The coin denominations
 * @param int $sum The countable sum
 * @return int
 */
function getTotalCombinations($money, $coins, &$sum = 0){
  if ($money == 0){
    return $sum++;
  } else if (empty($coins) || $money < 0){
    return $sum;
  } else {
      $firstCoin = array_pop(array_reverse($coins));
      getTotalCombinations($money - $firstCoin, $coins, $sum) + getTotalCombinations($money, array_diff($coins, [$firstCoin]), $sum);
  }
  return $sum;
}


$totalCombinations = getTotalCombinations($money, $coins);

Answer 8

PHP-код для разбивки суммы на номиналы:

//Define the denominations    
private $denominations = array(1000, 500, 200, 100, 50, 40, 20, 10, 5, 1);
/**
 * S# countDenomination() function
 * 
 * @author Edwin Mugendi <edwinmugendi@gmail.com>
 * 
 * Count denomination
 * 
 * @param float $original_amount Original amount
 * 
 * @return array with denomination and count
 */
public function countDenomination($original_amount) {
    $amount = $original_amount;
    $denomination_count_array = array();
    foreach ($this->denominations as $single_denomination) {

        $count = floor($amount / $single_denomination);

        $denomination_count_array[$single_denomination] = $count;

        $amount = fmod($amount, $single_denomination);
    }//E# foreach statement

    var_dump($denomination_count_array);
    return $denomination_count_array;
    //return $denomination_count_array;
}

// E # countDenomination () function

Answer 9

Ниже приведено решение Python:

    x = []
    dic = {}
    def f(n,r):
        [a,b,c,d] = r
        if not dic.has_key((n,a,b,c,d)): dic[(n,a,b,c,d)] = 1
        if n>=25:
            if not dic.has_key((n-25,a+1,b,c,d)):f(n-25,[a+1,b,c,d])
            if not dic.has_key((n-10,a,b+1,c,d)):f(n-10,[a,b+1,c,d])
            if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
            if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
        elif n>=10:
            if not dic.has_key((n-10,a,b+1,c,d)):f(n-10,[a,b+1,c,d])
            if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
            if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
        elif n>=5:
            if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
            if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
        elif n>=1:
            if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
        else:
            if r not in x:
                x.extend([r])

    f(100, [0,0,0,0])
    print x

Answer 10

Вот решение на основе Python, которое использует рекурсию и запоминание, что приводит к сложности O (mxn)

    def get_combinations_dynamic(self, amount, coins, memo):
    end_index = len(coins) - 1
    memo_key = str(amount)+'->'+str(coins)
    if memo_key in memo:
        return memo[memo_key]
    remaining_amount = amount
    if amount < 0:
        return []
    if amount == 0:
        return [[]]
    combinations = []
    if len(coins) <= 1:
        if amount % coins[0] == 0:
            combination = []
            for i in range(amount // coins[0]):
                combination.append(coins[0])
            list.sort(combination)
            if combination not in combinations:
                combinations.append(combination)
    else:
        k = 0
        while remaining_amount >= 0:
            sub_combinations = self.get_combinations_dynamic(remaining_amount, coins[:end_index], memo)
            for combination in sub_combinations:
                temp = combination[:]
                for i in range(k):
                    temp.append(coins[end_index])
                list.sort(temp)
                if temp not in combinations:
                    combinations.append(temp)
            k += 1
            remaining_amount -= coins[end_index]
    memo[memo_key] = combinations
    return combinations