Como encontrar todas as combinações de moedas quando dado algum valor em dólares

114

Encontrei um código que estava escrevendo para a preparação da entrevista alguns meses atrás.

De acordo com o comentário que fiz, estava tentando resolver este problema:

Dado algum valor em dólares em centavos (por exemplo, 200 = 2 dólares, 1000 = 10 dólares), encontre todas as combinações de moedas que compõem o valor em dólares. São permitidos apenas centavos (1 ¢), nickels (5 ¢), moedas (10 ¢) e quartos (25 ¢).

Por exemplo, se 100 foi fornecido, a resposta deve ser:

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

Eu acredito que isso pode ser resolvido de forma iterativa e recursiva. Minha solução recursiva tem muitos bugs, e eu queria saber como outras pessoas resolveriam esse problema. A parte difícil desse problema era torná-lo o mais eficiente possível.

codingbear
fonte
6
@akappa: penny = 1 cent; níquel = 5 centavos; dez centavos = 10 centavos; quarto = 25 centavos :)
codingbear
@John T: código de golfe? Nunca ouvi esse termo! De qualquer forma, espero ver algumas respostas interessantes, já que a comunidade SO pode resolver qualquer problema
codificação em
Também tentarei postar minha resposta assim que chegar em casa ... ainda no trabalho e não deveria perder muito tempo no SO.
codingbear
1
@blee code golf refere-se a resolver um problema com a menor quantidade de caracteres possível, com a linguagem de programação de sua escolha. Aqui estão algumas que foram feitas neste site: stackoverflow.com/search?q=code+golf
John T

Respostas:

54

Eu pesquisei isso uma vez, há muito tempo, e você pode ler meu pequeno artigo sobre isso . Aqui está a fonte do Mathematica .

Usando funções geradoras, você pode obter uma solução de tempo constante de forma fechada para o problema. Graham, Knuth e Patashnik's Concrete Mathematics é o livro para isso, e contém uma discussão bastante extensa do problema. Essencialmente, você define um polinômio onde o n- ésimo coeficiente é o número de maneiras de fazer alterações por n dólares.

As páginas 4-5 do artigo mostram como você pode usar o Mathematica (ou qualquer outro sistema de álgebra computacional conveniente) para calcular a resposta de 10 ^ 10 ^ 6 dólares em alguns segundos em três linhas de código.

(E isso foi há muito tempo que são alguns segundos em um Pentium 75 MHz ...)

andrewdotn
fonte
16
Boa resposta, mas problemas menores: observe que (1) Isso dá o número de maneiras, enquanto por alguma razão a questão pede o conjunto real de todas as maneiras. Claro, não pode haver nenhuma maneira de encontrar o conjunto em tempo polinomial, uma vez que a própria saída tem muitas entradas superpolinomialmente (2) É discutível se uma função geradora é uma "forma fechada" (veja o maravilhoso livro de Herbert Wilf Generatingfunctionology : math. upenn.edu/~wilf/DownldGF.html ) e se você quer dizer uma expressão como (1 + √5) ^ n, leva Ω (log n) tempo para calcular, não um tempo constante.
ShreevatsaR
Introdução suave à programação dinâmica. Além disso, encorajo qualquer pessoa com um problema de sequência a ler a funcionalidade de geração .
Coronel Panic
Muito obrigado, Andrew ... esta explicação me ajudou muito ... Postando a função scala abaixo .. se alguém precisar
jayaram S
1
Acredito que a pergunta inicial precise de uma ligeira correção porque pergunta "... usando moedas de 1, 10, 25, 50 e 100 centavos?" Mas então a redação define o conjunto acomo o domínio de fmas a = {1,5,10,25,50,100}. Deve haver um 5 na lista de moedas de centavo. Fora isso, o artigo foi fantástico, obrigado!
rbrtl
@rbrtl Uau, você está certo, obrigado por notar isso! Vou atualizá-lo ...
andrewdotn
42

Nota : Isso mostra apenas o número de maneiras.

Função 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)
Vlad
fonte
1
Existe realmente uma maneira de alterar 0? Acho que não há como fazer isso.
Lucas
2
Decorre do número de soluções polinomiais n1 * coins(0) + n2 * coins(1) + ... + nN * coins(N-1) = money. Portanto, para money=0e coins=List(1,2,5,10)a contagem para combinações (n1, n2, n3, n4)é 1 e a solução é (0, 0, 0, 0).
Kyr de
3
Não consigo entender por que essa implementação funciona. Alguém pode me explicar o algoritmo por trás?
Adrien Lemaire
3
Esta é definitivamente a resposta exata ao problema 3 do exercício 1 do curso coursera scala.
Justin Standard
Eu acredito que, se money == 0mas coins.isEmpty, não deveria contar como um sol'n. Portanto, o algoritmo pode ser melhor atendido se a coins.isEmpty || money < 0condição for examinada primeiro.
juanchito de
26

Eu seria a favor de uma solução recursiva. Você tem alguma lista de denominações, se a menor delas puder dividir igualmente qualquer valor de moeda restante, isso deve funcionar bem.

Basicamente, você passa das denominações maiores para as menores.
Recursivamente,

  1. Você tem um total atual para preencher e uma denominação maior (com mais de 1 restante). Se sobrar apenas 1 denominação, só há uma forma de preencher o total. Você pode usar de 0 a k cópias de sua denominação atual de forma que k * cur denominação <= total.
  2. Para 0 a k, chame a função com o total modificado e a nova maior denominação.
  3. Some os resultados de 0 a k. Estas são de quantas maneiras você pode preencher seu total da denominação atual para baixo. Devolva este número.

Aqui está minha versão python do seu problema declarado, por 200 centavos. Eu recebo 1463 maneiras. Esta versão imprime todas as combinações e o total da contagem final.

#!/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)
Leif
fonte
Ainda não o executei, mas seguindo sua lógica, faz sentido :)
codingbear
Você pode substituir as duas últimas linhas da função por "return sum (count_combs (...) for ...)" - dessa forma, a lista não se materializa. :)
Nick Johnson
Obrigado pela dica. Estou sempre interessado em maneiras de restringir o código.
leif
2
Conforme discutido em outra questão , este código dará saída incorreta se a lista de denominationsnão tiver 1como último valor. Você pode adicionar uma pequena quantidade de código ao ifbloco mais interno para corrigi-lo (conforme descrevo em minha resposta à outra pergunta).
Blckknght
12

Função 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
}
Jayaram S
fonte
Obrigado! Este é um grande começo. Mas, eu acho que isso falha quando "dinheiro" começa sendo 0 :).
aqn
10

Aqui estão alguns códigos C ++ absolutamente diretos para resolver o problema que exigia que todas as combinações fossem mostradas.

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

Mas estou bastante intrigado com o problema secundário de apenas calcular o número de combinações. Suspeito que haja uma equação de forma fechada para isso.

George Phillips
fonte
9
Certamente isso é C, não C ++.
nikhil
1
@George Phillips, você pode explicar?
Tentando em
Eu acho que é muito simples. Basicamente, a ideia é iterar todos os trimestres (usando 0,1,2 .. máx.) E, em seguida, iterar todas as moedas com base nos trimestres usados, etc.
Peter Lee
4
A desvantagem desta solução é: se houver moedas de 50 centavos, 100 centavos, 500 centavos, então temos que usar loops de 6 níveis ...
Peter Lee
3
Isso é muito ruim, se você tem denominações dinâmicas ou deseja adicionar outra denominação, então não funcionará.
shinzou de
7

O subproblema é um problema típico de Programação Dinâmica.

/* 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;
}
Peter Lee
fonte
Suas soluções dinâmicas requerem k para ter o comprimento de C menos 1. um pouco confuso. Você pode alterá-lo facilmente para suportar o comprimento real de C.
Idan
7

O código está usando Java para resolver esse problema e também funciona ... Esse método pode não ser uma boa ideia por causa de muitos loops, mas é realmente uma maneira direta.

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

Esta é uma questão muito antiga, mas eu vim com uma solução recursiva em java que parecia menor do que todas as outras, então aqui vai -

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

Melhorias:

  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);
        }
     }
Rohit Pandey
fonte
6

Seja C (i, J) o conjunto de combinações de fazer i centavos usando os valores do conjunto J.

Você pode definir C assim:

insira a descrição da imagem aqui

(primeiro (J) assume de forma determinística um elemento de um conjunto)

Acontece uma função bastante recursiva ... e razoavelmente eficiente se você usar memoização;)

Akappa
fonte
Sim, isso ("programação dinâmica", em certo sentido) vai ser a solução ideal.
ShreevatsaR
você está certo: tome J como uma lista e não como um conjunto: então primeiro (J) traz para você o primeiro elemento e J \ first (J) dá para você o resto da lista.
akappa
que forma de matemática é essa?
Muhammad Umer
5

semi-hack para contornar o problema de combinação única - forçar ordem decrescente:

$ denoms = [1,5,10,25]
def all_combs (soma, último) 
  retorna 1 se soma == 0
  return $ denoms.select {| d | d & le sum && d & le last} .inject (0) {| total, denom |
           total + all_combs (soma-denom, denom)}
fim

Isso ficará lento, pois não será memorizado, mas essa é a ideia.

Klochner
fonte
4
# short and sweet with O(n) table memory    

#include <iostream>
#include <vector>

int count( std::vector<int> s, int n )
{
  std::vector<int> table(n+1,0);

  table[0] = 1;
  for ( auto& k : s )
    for(int j=k; j<=n; ++j)
      table[j] += table[j-k];

  return table[n];
}

int main()
{
  std::cout <<  count({25, 10, 5, 1}, 100) << std::endl;
  return 0;
}
3 rotações
fonte
3

Esta é minha resposta em Python. Não usa recursão:

def crossprod (list1, list2):
    output = 0
    for i in range(0,len(list1)):
        output += list1[i]*list2[i]

    return output

def breakit(target, coins):
    coinslimit = [(target / coins[i]) for i in range(0,len(coins))]
    count = 0
    temp = []
    for i in range(0,len(coins)):
        temp.append([j for j in range(0,coinslimit[i]+1)])


    r=[[]]
    for x in temp:
        t = []
        for y in x:
            for i in r:
                t.append(i+[y])
        r = t

    for targets in r:
        if crossprod(targets, coins) == target:
            print targets
            count +=1
    return count




if __name__ == "__main__":
    coins = [25,10,5,1]
    target = 78
    print breakit(target, coins)

Saída de exemplo

    ...
    1 ( 10 cents)  2 ( 5 cents)  58 ( 1 cents)  
    4 ( 5 cents)  58 ( 1 cents)  
    1 ( 10 cents)  1 ( 5 cents)  63 ( 1 cents)  
    3 ( 5 cents)  63 ( 1 cents)  
    1 ( 10 cents)  68 ( 1 cents)  
    2 ( 5 cents)  68 ( 1 cents)  
    1 ( 5 cents)  73 ( 1 cents)  
    78 ( 1 cents)  
    Number of solutions =  121
Marca
fonte
3
var countChange = function (money,coins) {
  function countChangeSub(money,coins,n) {
    if(money==0) return 1;
    if(money<0 || coins.length ==n) return 0;
    return countChangeSub(money-coins[n],coins,n) + countChangeSub(money,coins,n+1);
  }
  return countChangeSub(money,coins,0);
}
jasonhao
fonte
2

Ambos: itera através de todas as denominações de alto a baixo, pegue um de denominação, subtraia do total solicitado e, em seguida, repasse no restante (restringindo denominações disponíveis para serem iguais ou menores ao valor de iteração atual).

djna
fonte
2

Se o sistema monetário permitir, um algoritmo simples e ganancioso que pega o máximo possível de cada moeda, começando com a moeda de maior valor.

Caso contrário, a programação dinâmica é necessária para encontrar uma solução ótima rapidamente, uma vez que este problema é essencialmente o problema da mochila .

Por exemplo, se um sistema monetário tem as moedas {13, 8, 1}:, a solução gananciosa faria a troca por 24 as {13, 8, 1, 1, 1}, mas a verdadeira solução ótima é{8, 8, 8}

Edit: Achei que estávamos fazendo a mudança de forma otimizada, não listando todas as maneiras de fazer a mudança por um dólar. Minha entrevista recente perguntou como fazer a mudança, então pulei em frente antes de terminar de ler a pergunta.

Ben S
fonte
o problema não é necessariamente de um dólar - pode ser 2 ou 23, portanto, sua solução ainda é a única correta.
Neil G de
2

Eu sei que esta é uma questão muito antiga. Eu estava procurando a resposta correta e não consegui encontrar nada que fosse simples e satisfatório. Levei algum tempo, mas fui capaz de anotar algo.

function denomination(coins, original_amount){
    var original_amount = original_amount;
    var original_best = [ ];

    for(var i=0;i<coins.length; i++){
      var amount = original_amount;
      var best = [ ];
      var tempBest = [ ]
      while(coins[i]<=amount){
        amount = amount - coins[i];
        best.push(coins[i]);
      }
      if(amount>0 && coins.length>1){
        tempBest = denomination(coins.slice(0,i).concat(coins.slice(i+1,coins.length)), amount);
        //best = best.concat(denomination(coins.splice(i,1), amount));
      }
      if(tempBest.length!=0 || (best.length!=0 && amount==0)){
        best = best.concat(tempBest);
        if(original_best.length==0 ){
          original_best = best
        }else if(original_best.length > best.length ){
          original_best = best;
        }  
      }
    }
    return original_best;  
  }
  denomination( [1,10,3,9] , 19 );

Esta é uma solução javascript e usa recursão.

Varun
fonte
Esta solução encontra apenas uma denominação. A questão era encontrar "todas" as denominações.
heinob de
2

Na linguagem de programação Scala, eu faria assim:

 def countChange(money: Int, coins: List[Int]): Int = {

       money match {
           case 0 => 1
           case x if x < 0 => 0
           case x if x >= 1 && coins.isEmpty => 0
           case _ => countChange(money, coins.tail) + countChange(money - coins.head, coins)

       }

  }
MrOnyancha
fonte
2

Este é um algoritmo recursivo simples que pega uma nota e, em seguida, pega uma nota menor recursivamente até atingir a soma, então pega outra nota da mesma denominação e recorre novamente. Veja o exemplo de saída abaixo para ilustração.

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, "");

Imprime o seguinte:

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
user7431997
fonte
1

Duh, me sinto estúpido agora. Abaixo, há uma solução excessivamente complicada, que preservarei porque , afinal, é uma solução. Uma solução simples seria esta:

// Generate a pretty string
val coinNames = List(("quarter", "quarters"), 
                     ("dime", "dimes"), 
                     ("nickel", "nickels"), 
                     ("penny", "pennies"))
def coinsString = 
  Function.tupled((quarters: Int, dimes: Int, nickels:Int, pennies: Int) => (
    List(quarters, dimes, nickels, pennies) 
    zip coinNames // join with names
    map (t => (if (t._1 != 1) (t._1, t._2._2) else (t._1, t._2._1))) // correct for number
    map (t => t._1 + " " + t._2) // qty name
    mkString " "
  ))

def allCombinations(amount: Int) = 
 (for{quarters <- 0 to (amount / 25)
      dimes <- 0 to ((amount - 25*quarters) / 10)
      nickels <- 0 to ((amount - 25*quarters - 10*dimes) / 5)
  } yield (quarters, dimes, nickels, amount - 25*quarters - 10*dimes - 5*nickels)
 ) map coinsString mkString "\n"

Aqui está a outra solução. Esta solução baseia-se na observação de que cada moeda é um múltiplo das outras, para que possam ser representadas em termos delas.

// Just to make things a bit more readable, as these routines will access
// arrays a lot
val coinValues = List(25, 10, 5, 1)
val coinNames = List(("quarter", "quarters"), 
                     ("dime", "dimes"), 
                     ("nickel", "nickels"), 
                     ("penny", "pennies"))
val List(quarter, dime, nickel, penny) = coinValues.indices.toList


// Find the combination that uses the least amount of coins
def leastCoins(amount: Int): Array[Int] =
  ((List(amount) /: coinValues) {(list, coinValue) =>
    val currentAmount = list.head
    val numberOfCoins = currentAmount / coinValue
    val remainingAmount = currentAmount % coinValue
    remainingAmount :: numberOfCoins :: list.tail
  }).tail.reverse.toArray

// Helper function. Adjust a certain amount of coins by
// adding or subtracting coins of each type; this could
// be made to receive a list of adjustments, but for so
// few types of coins, it's not worth it.
def adjust(base: Array[Int], 
           quarters: Int, 
           dimes: Int, 
           nickels: Int, 
           pennies: Int): Array[Int] =
  Array(base(quarter) + quarters, 
        base(dime) + dimes, 
        base(nickel) + nickels, 
        base(penny) + pennies)

// We decrease the amount of quarters by one this way
def decreaseQuarter(base: Array[Int]): Array[Int] =
  adjust(base, -1, +2, +1, 0)

// Dimes are decreased this way
def decreaseDime(base: Array[Int]): Array[Int] =
  adjust(base, 0, -1, +2, 0)

// And here is how we decrease Nickels
def decreaseNickel(base: Array[Int]): Array[Int] =
  adjust(base, 0, 0, -1, +5)

// This will help us find the proper decrease function
val decrease = Map(quarter -> decreaseQuarter _,
                   dime -> decreaseDime _,
                   nickel -> decreaseNickel _)

// Given a base amount of coins of each type, and the type of coin,
// we'll produce a list of coin amounts for each quantity of that particular
// coin type, up to the "base" amount
def coinSpan(base: Array[Int], whichCoin: Int) = 
  (List(base) /: (0 until base(whichCoin)).toList) { (list, _) =>
    decrease(whichCoin)(list.head) :: list
  }

// Generate a pretty string
def coinsString(base: Array[Int]) = (
  base 
  zip coinNames // join with names
  map (t => (if (t._1 != 1) (t._1, t._2._2) else (t._1, t._2._1))) // correct for number
  map (t => t._1 + " " + t._2)
  mkString " "
)

// So, get a base amount, compute a list for all quarters variations of that base,
// then, for each combination, compute all variations of dimes, and then repeat
// for all variations of nickels.
def allCombinations(amount: Int) = {
  val base = leastCoins(amount)
  val allQuarters = coinSpan(base, quarter)
  val allDimes = allQuarters flatMap (base => coinSpan(base, dime))
  val allNickels = allDimes flatMap (base => coinSpan(base, nickel))
  allNickels map coinsString mkString "\n"
}

Então, para 37 moedas, por exemplo:

scala> println(allCombinations(37))
0 quarter 0 dimes 0 nickels 37 pennies
0 quarter 0 dimes 1 nickel 32 pennies
0 quarter 0 dimes 2 nickels 27 pennies
0 quarter 0 dimes 3 nickels 22 pennies
0 quarter 0 dimes 4 nickels 17 pennies
0 quarter 0 dimes 5 nickels 12 pennies
0 quarter 0 dimes 6 nickels 7 pennies
0 quarter 0 dimes 7 nickels 2 pennies
0 quarter 1 dime 0 nickels 27 pennies
0 quarter 1 dime 1 nickel 22 pennies
0 quarter 1 dime 2 nickels 17 pennies
0 quarter 1 dime 3 nickels 12 pennies
0 quarter 1 dime 4 nickels 7 pennies
0 quarter 1 dime 5 nickels 2 pennies
0 quarter 2 dimes 0 nickels 17 pennies
0 quarter 2 dimes 1 nickel 12 pennies
0 quarter 2 dimes 2 nickels 7 pennies
0 quarter 2 dimes 3 nickels 2 pennies
0 quarter 3 dimes 0 nickels 7 pennies
0 quarter 3 dimes 1 nickel 2 pennies
1 quarter 0 dimes 0 nickels 12 pennies
1 quarter 0 dimes 1 nickel 7 pennies
1 quarter 0 dimes 2 nickels 2 pennies
1 quarter 1 dime 0 nickels 2 pennies
Daniel C. Sobral
fonte
1

Esta entrada do meu blog resolve esse problema tipo mochila para as figuras de uma história em quadrinhos do XKCD . Uma simples mudança no itemsdict e no exactcostvalor resultará em todas as soluções para o seu problema também.

Se o problema fosse encontrar a mudança que usava o menor custo, então um algoritmo ingênuo e ganancioso que usava tanto da moeda de maior valor poderia falhar para algumas combinações de moedas e valor alvo. Por exemplo, se houver moedas com os valores 1, 3 e 4; e a quantidade desejada é 6, então o algoritmo ganancioso pode sugerir três moedas de valor 4, 1 e 1 quando for fácil ver que você pode usar duas moedas de valor 3 cada.

  • Paddy.
Paddy3118
fonte
1
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);                     
                }                   
            }                   
        }           
    }       
}
 }
Amit Patil
fonte
1

Eu encontrei esse código legal no livro "Python For Data Analysis", de O'reily. Ele usa implementação preguiçosa e comparação interna e presumo que possa ser modificado para outras denominações usando decimais. Deixe-me saber como funciona para você!

def make_change(amount, coins=[1, 5, 10, 25], hand=None):
 hand = [] if hand is None else hand
 if amount == 0:
 yield hand
 for coin in coins:
 # ensures we don't give too much change, and combinations are unique
 if coin > amount or (len(hand) > 0 and hand[-1] < coin):
 continue
 for result in make_change(amount - coin, coins=coins,
 hand=hand + [coin]):
 yield result

Suhas
fonte
1

Essa é a melhora da resposta de Zihan. A grande quantidade de loops desnecessários ocorre quando a denominação é de apenas 1 centavo.

É intuitivo e não recursivo.

    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;            
    }
Aerin
fonte
Você não pode generalizar esta solução, então, por exemplo, um novo elemento surge; nesse caso, você deve adicionar outro loop for
Sumit Kumar Saha
1

Solução java simples:

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;
  }
}
GR44
fonte
1
/*
* 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;
}
rpk
fonte
1

Aqui está uma função 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));
    }

Use-o assim:

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

Ele imprime:

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
Shinzou
fonte
O resultado é bonito
Obrigado
1

Abaixo está um programa python para encontrar todas as combinações de dinheiro. Esta é uma solução de programação dinâmica com tempo de ordem (n). O dinheiro é 1,5,10,25

Atravessamos a moeda 1 para a moeda 25 (4 linhas). O dinheiro da linha 1 contém a contagem se considerarmos apenas o dinheiro 1 no cálculo do número de combinações. O dinheiro da linha 5 produz cada coluna pegando a contagem do dinheiro da linha r para o mesmo dinheiro final mais a contagem das 5 anteriores em sua própria linha (posição atual menos 5). Dinheiro de linha 10 usa dinheiro de linha 5, que contém contagens de 1,5 e soma na contagem de 10 anteriores (posição atual menos 10). Dinheiro de linha 25 usa dinheiro de linha 10, que contém contagens para dinheiro de linha 1,5,10 mais a contagem de 25 anteriores.

Por exemplo, números [1] [12] = números [0] [12] + números [1] [7] (7 = 12-5) que resulta em 3 = 1 + 2; números [3] [12] = números [2] [12] + números [3] [9] (-13 = 12-25) que resulta em 4 = 0 + 4, já que -13 é menor que 0.

def cntMoney(num):
    mSz = len(money)
    numbers = [[0]*(1+num) for _ in range(mSz)]
    for mI in range(mSz): numbers[mI][0] = 1
    for mI,m in enumerate(money):
        for i in range(1,num+1):
            numbers[mI][i] = numbers[mI][i-m] if i >= m else 0
            if mI != 0: numbers[mI][i] += numbers[mI-1][i]
        print('m,numbers',m,numbers[mI])
    return numbers[mSz-1][num]

money = [1,5,10,25]
    num = 12
    print('money,combinations',num,cntMoney(num))

output:    
('m,numbers', 1, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
('m,numbers', 5, [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3])
('m,numbers', 10, [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4])
('m,numbers', 25, [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4])
('money,combinations', 12, 4)
edW
fonte
0

Solução Java

import java.util.Arrays;
import java.util.Scanner;


public class nCents {



public static void main(String[] args) {

    Scanner input=new Scanner(System.in);
    int cents=input.nextInt();
    int num_ways [][] =new int [5][cents+1];

    //putting in zeroes to offset
    int getCents[]={0 , 0 , 5 , 10 , 25};
    Arrays.fill(num_ways[0], 0);
    Arrays.fill(num_ways[1], 1);

    int current_cent=0;
    for(int i=2;i<num_ways.length;i++){

        current_cent=getCents[i];

        for(int j=1;j<num_ways[0].length;j++){
            if(j-current_cent>=0){
                if(j-current_cent==0){
                    num_ways[i][j]=num_ways[i-1][j]+1;
                }else{
                    num_ways[i][j]=num_ways[i][j-current_cent]+num_ways[i-1][j];
                }
            }else{
                num_ways[i][j]=num_ways[i-1][j];
            }


        }


    }



    System.out.println(num_ways[num_ways.length-1][num_ways[0].length-1]);

}

}

O urso
fonte
0

A solução Java abaixo que também imprimirá as diferentes combinações. Fácil de entender. Ideia é

para soma 5

A solução é

    5 - 5(i) times 1 = 0
        if(sum = 0)
           print i times 1
    5 - 4(i) times 1 = 1
    5 - 3 times 1 = 2
        2 -  1(j) times 2 = 0
           if(sum = 0)
              print i times 1 and j times 2
    and so on......

Se a soma restante em cada loop for menor do que a denominação, ou seja, se a soma restante 1 for menor que 2, basta interromper o loop

O código completo abaixo

Por favor, me corrija em caso de algum erro

public class CoinCombinbationSimple {
public static void main(String[] args) {
    int sum = 100000;
    printCombination(sum);
}

static void printCombination(int sum) {
    for (int i = sum; i >= 0; i--) {
        int sumCopy1 = sum - i * 1;
        if (sumCopy1 == 0) {
            System.out.println(i + " 1 coins");
        }
        for (int j = sumCopy1 / 2; j >= 0; j--) {
            int sumCopy2 = sumCopy1;
            if (sumCopy2 < 2) {
                break;
            }
            sumCopy2 = sumCopy1 - 2 * j;
            if (sumCopy2 == 0) {
                System.out.println(i + " 1 coins " + j + " 2 coins ");
            }
            for (int k = sumCopy2 / 5; k >= 0; k--) {
                int sumCopy3 = sumCopy2;
                if (sumCopy2 < 5) {
                    break;
                }
                sumCopy3 = sumCopy2 - 5 * k;
                if (sumCopy3 == 0) {
                    System.out.println(i + " 1 coins " + j + " 2 coins "
                            + k + " 5 coins");
                }
            }
        }
    }
}

}

Padre Mathew
fonte
0

Aqui está uma solução baseada em Python que usa recursão, bem como memoização, resultando em uma complexidade de 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
lalatnayak
fonte
Ok, eu duvido que o acima tenha tempo de execução polinomial. Não tenho certeza se podemos ter tempo de execução polinomial. Mas o que observei é que a versão acima é executada mais rápido do que a versão não memorizada em muitos casos. Vou continuar pesquisando o porquê
lalatnayak