Jak znaleźć wszystkie kombinacje monet, mając określoną wartość w dolarach

114

Kilka miesięcy temu znalazłem fragment kodu, który przygotowywałem do rozmowy kwalifikacyjnej.

Zgodnie z komentarzem, który miałem, próbował rozwiązać ten problem:

Biorąc pod uwagę wartość dolara w centach (np. 200 = 2 dolary, 1000 = 10 dolarów), znajdź wszystkie kombinacje monet, które składają się na wartość dolara. Dozwolone są tylko grosze (1 ¢), 5 centów (5 centów), dziesięciocentówki (10 centów) i ćwiartki (25 centów).

Na przykład, jeśli podano 100, odpowiedź powinna brzmieć:

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

Uważam, że można to rozwiązać w sposób iteracyjny i rekurencyjny. Moje rozwiązanie rekurencyjne jest dość błędne i zastanawiałem się, jak inni ludzie mogą rozwiązać ten problem. Trudną częścią tego problemu było zapewnienie jak największej wydajności.

codingbear
źródło
6
@akappa: pens = 1 cent; nikiel = 5 centów; dime = 10 centów; kwartał = 25 centów :)
codingbear
@John T: kod golfa? Nigdy nie słyszałem o tym terminie! W każdym razie, mam nadzieję, że zobaczę kilka interesujących odpowiedzi, ponieważ społeczność SO może rozwiązać każdy problem
codingbear
Spróbuję też zamieścić swoją odpowiedź, gdy wrócę do domu ... nadal w pracy i nie powinienem spędzać zbyt wiele czasu na SO.
codingbear
1
@blee code golf odnosi się do rozwiązywania problemu przy użyciu możliwie najmniejszej liczby znaków, w wybranym przez Ciebie języku programowania. Oto niektóre, które zostały zrobione na tej stronie: stackoverflow.com/search?q=code+golf
John T

Odpowiedzi:

54

Zajrzałem do tego kiedyś dawno temu i możesz przeczytać o tym mój mały opis . Oto źródło Mathematica .

Korzystając z funkcji generujących, można uzyskać rozwiązanie problemu w postaci zamkniętej w stałym czasie. Książka Grahama, Knutha i Patashnika Concrete Mathematics jest książką poświęconą temu zagadnieniu i zawiera dość obszerne omówienie problemu. Zasadniczo definiujesz wielomian, w którym n- ty współczynnik jest liczbą sposobów dokonywania zmiany dla n dolarów.

Strony 4-5 zapisu pokazują, jak można użyć Mathematica (lub innego wygodnego systemu algebry komputerowej) do obliczenia odpowiedzi za 10 ^ 10 ^ 6 dolarów w ciągu kilku sekund w trzech wierszach kodu.

(I to było wystarczająco dawno temu, że to kilka sekund na 75Mhz Pentium ...)

andrewdotn
źródło
16
Dobra odpowiedź, ale drobne zastrzeżenia: zauważ, że (1) Podaje liczbę sposobów, podczas gdy z jakiegoś powodu pytanie dotyczy rzeczywistego zestawu wszystkich sposobów. Oczywiście nie ma możliwości znalezienia zbioru w czasie wielomianowym, ponieważ samo wyjście ma wielomianowo wiele wpisów (2) Jest dyskusyjne, czy funkcja generująca jest „formą zamkniętą” (patrz wspaniała książka Herberta Wilfa Generatingfunctionology : math. upenn.edu/~wilf/DownldGF.html ) i jeśli masz na myśli wyrażenie takie jak (1 + √5) ^ n, obliczenie zajmuje Ω (log n) czasu, a nie stały czas.
ShreevatsaR
Delikatne wprowadzenie do programowania dynamicznego. Zachęcam również każdego, kto ma problem z sekwencją, do przeczytania funkcji generowania .
Colonel Panic
Dziękuję bardzo Andrew ... to wyjaśnienie bardzo mi pomogło ... Umieszczanie poniżej funkcji scala .. gdyby ktoś jej potrzebował
jayaram S
1
Uważam, że pytanie na początku wymaga niewielkiej korekty, ponieważ brzmi „… używając monet 1-, 10-, 25-, 50- i 100-centowych?” Ale potem zapis definiuje zbiór ajako domenę fale a = {1,5,10,25,50,100}. Na liście monet powinno znajdować się 5 centów. W przeciwnym razie opis był fantastyczny, dzięki!
rbrtl
@rbrtl Wow, masz rację, dzięki, że to zauważyłeś! Zaktualizuję to…
andrewdotn
42

Uwaga : pokazuje tylko liczbę sposobów.

Funkcja 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
źródło
1
Czy naprawdę istnieje jeden sposób, aby zmienić 0? Chyba nie da się tego zrobić.
Łukasz
2
Wynika to z liczby rozwiązań wielomianowych n1 * coins(0) + n2 * coins(1) + ... + nN * coins(N-1) = money. Więc dla money=0i coins=List(1,2,5,10)liczba kombinacji (n1, n2, n3, n4)wynosi 1, a rozwiązaniem jest (0, 0, 0, 0).
Kyr
3
Nie mogę pojąć, dlaczego ta implementacja działa. Czy ktoś może mi wyjaśnić algorytm stojący za nim?
Adrien Lemaire
3
To jest z pewnością dokładna odpowiedź na problem 3 ćwiczenia 1 kursu coursera scala.
Justin Standard
Uważam, że jeśli money == 0ale coins.isEmpty, to nie powinno się liczyć jako rozwiązanie. Dlatego też algo może być lepiej obsługiwane, jeśli coins.isEmpty || money < 0warunek zostanie ck'd jako pierwszy.
juanchito
26

Wolałbym rozwiązanie rekurencyjne. Masz listę nominałów, jeśli najmniejszy może równo podzielić pozostałą kwotę waluty, powinno to działać dobrze.

Zasadniczo przechodzisz od największych do najmniejszych nominałów.
Rekurencyjnie,

  1. Masz aktualną sumę do wypełnienia i największy nominał (pozostało więcej niż 1). Jeśli pozostał tylko 1 nominał, jest tylko jeden sposób na wypełnienie sumy. Możesz użyć od 0 do k kopii swojego aktualnego nominału, tak że k * aktualny nominał <= suma.
  2. Od 0 do k wywołaj funkcję ze zmodyfikowaną sumą i nowym największym nominałem.
  3. Dodaj wyniki od 0 do k. Oto ile sposobów możesz wypełnić swoją sumę od aktualnego nominału w dół. Zwróć ten numer.

Oto moja wersja Twojego problemu w Pythonie za 200 centów. Mam 1463 sposoby. Ta wersja wypisuje wszystkie kombinacje i ostateczną liczbę.

#!/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
źródło
Nie uruchomiłem tego, ale przechodząc przez twoją logikę, ma to sens :)
codingbear
Możesz zamienić ostatnie dwa wiersze funkcji na "return sum (count_combs (...) for ...)" - w ten sposób lista nie zostanie w ogóle zmaterializowana. :)
Nick Johnson,
Dzięki za wskazówkę. Zawsze jestem zainteresowany sposobami ulepszenia kodu.
leif
2
Jak omówiono w innym pytaniu , ten kod da niepoprawne dane wyjściowe, jeśli lista denominationsnie ma 1jako ostatniej wartości. Możesz dodać niewielką ilość kodu do najbardziej wewnętrznego ifbloku, aby to naprawić (jak opisuję w mojej odpowiedzi na inne pytanie).
Blckknght
12

Funkcja 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
źródło
Dzięki! To świetny początek. Ale myślę, że to się nie udaje, kiedy „pieniądze” zaczynają się od 0 :).
aqn
10

Oto absolutnie prosty kod w C ++ rozwiązujący problem, który wymagał wyświetlenia wszystkich kombinacji.

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

Ale jestem dość zaintrygowany problemem podrzędnym polegającym na obliczaniu liczby kombinacji. Podejrzewam, że istnieje na to równanie w postaci zamkniętej.

George Phillips
źródło
9
Z pewnością jest to C, a nie C ++.
nikhil
1
@George Phillips, czy możesz wyjaśnić?
Próba
Myślę, że to całkiem proste. Zasadniczo chodzi o to, aby iterować wszystkie ćwiartki (używając 0,1,2 .. max), a następnie iterować przez wszystkie dziesięciocentówki na podstawie użytych ćwiartek itd.
Peter Lee
4
Wadą tego rozwiązania jest to, że jeśli są monety 50-centowe, 100-centowe, 500-centowe, to musimy użyć 6-poziomowych pętli ...
Peter Lee
3
To jest bardzo złe, jeśli masz dynamiczne nominały lub chcesz dodać inny nominał, to nie zadziała.
shinzou
7

Problem podrzędny jest typowym problemem programowania dynamicznego.

/* 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
źródło
Twoje rozwiązania dynamiczne wymagają, aby k było długością C minus 1. Trochę mylące. Możesz to łatwo zmienić, aby obsługiwać rzeczywistą długość C.
Idan
7

Kod wykorzystuje Javę do rozwiązania tego problemu i działa również ... Ta metoda może nie być dobrym pomysłem z powodu zbyt wielu pętli, ale jest to naprawdę prosta droga.

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
źródło
7

To jest naprawdę stare pytanie, ale wymyśliłem rozwiązanie rekurencyjne w Javie, które wydawało się mniejsze niż wszystkie inne, więc oto -

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

Ulepszenia:

  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
źródło
6

Niech C (i, J) jest zbiorem kombinacji tworzenia i centów przy użyciu wartości ze zbioru J.

Możesz zdefiniować C jako:

wprowadź opis obrazu tutaj

(pierwszy (J) przyjmuje w deterministyczny sposób element zbioru)

Okazuje się, że jest to dość rekurencyjna funkcja ... i dość wydajna, jeśli używasz zapamiętywania;)

akappa
źródło
Tak, to (w pewnym sensie „programowanie dynamiczne”) będzie optymalnym rozwiązaniem.
ShreevatsaR
masz rację: weź J jako listę, a nie jako zbiór: potem najpierw (J) przynosi ci pierwszy element, a J \ pierwszy (J) daje ci resztę listy.
akappa,
jaka to forma matematyki?
Muhammad Umer
5

pół-hack, aby obejść problem unikalnej kombinacji - wymuś kolejność malejącą:

$ denoms = [1,5,10,25]
def all_combs (suma, ostatnia) 
  zwraca 1, jeśli suma == 0
  return $ denoms.select {| d | d & le sum && d & le last} .inject (0) {| total, denom |
           total + all_combs (suma-denom, denom)}
koniec

Będzie to działać wolno, ponieważ nie zostanie zapamiętane, ale masz pomysł.

klochner
źródło
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;
}
bjackfly
źródło
3

To jest moja odpowiedź w Pythonie. Nie używa rekurencji:

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)

Przykładowe dane wyjściowe

    ...
    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
znak
źródło
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
źródło
2

Obie: iteruj przez wszystkie nominały od najwyższego do najniższego, weź jeden z nominałów, odejmij od wymaganej sumy, a następnie powtórz na pozostałej części (ograniczając dostępne nominały, aby były równe lub niższe od bieżącej wartości iteracji).

djna
źródło
2

Jeśli system walutowy na to pozwala, prosty chciwy algorytm który pobiera jak najwięcej monet, zaczynając od waluty o najwyższej wartości.

W przeciwnym razie, aby szybko znaleźć optymalne rozwiązanie, wymagane jest programowanie dynamiczne, ponieważ ten problem jest zasadniczo problemem plecaka .

Na przykład, jeśli system walutowy ma monety {13, 8, 1}:, chciwe rozwiązanie spowodowałoby zmianę za 24 as {13, 8, 1, 1, 1}, ale prawdziwym optymalnym rozwiązaniem jest{8, 8, 8}

Edycja: Myślałem, że wprowadzamy zmiany optymalnie, a nie wymieniamy wszystkie sposoby wprowadzenia zmiany za dolara. W moim ostatnim wywiadzie zapytałem, jak wprowadzić zmiany, więc odskoczyłem do przodu, zanim skończyłem czytać pytanie.

Ben S.
źródło
problem niekoniecznie dotyczy jednego dolara - może to być 2 lub 23, więc twoje rozwiązanie jest nadal jedyne poprawne.
Neil G,
2

Wiem, że to bardzo stare pytanie. Szukałem właściwej odpowiedzi i nie mogłem znaleźć niczego prostego i satysfakcjonującego. Zajęło mi to trochę czasu, ale udało mi się coś zapisać.

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

To jest rozwiązanie javascript i używa rekursji.

varun
źródło
To rozwiązanie znajduje tylko jeden nominał. Chodziło o znalezienie „wszystkich” wyznań.
heinob
2

W języku programowania Scala zrobiłbym to tak:

 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
źródło
2

Jest to prosty algorytm rekurencyjny, który pobiera rachunek, a następnie rekurencyjnie pobiera mniejszy rachunek, aż osiągnie sumę, następnie bierze kolejny weksel o tym samym nominale i ponownie powtarza. Zobacz przykładowe dane wyjściowe poniżej dla ilustracji.

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

Drukuje:

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
źródło
1

Duh, czuję się teraz głupio. Poniżej znajduje się zbyt skomplikowane rozwiązanie, które będę zachować, gdyż jest to rozwiązanie, mimo wszystko. Prostym rozwiązaniem byłoby to:

// 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"

Oto inne rozwiązanie. To rozwiązanie opiera się na obserwacji, że każda moneta jest wielokrotnością pozostałych, więc można je przedstawić w ich kategoriach.

// 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"
}

Na przykład za 37 monet:

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
źródło
1

Ten mój wpis na blogu rozwiązuje ten plecakowy problem z postaciami z komiksu XKCD . Prosta zmiana w itemsdyktandzie i exactcostwartości przyniesie również wszystkie rozwiązania twojego problemu.

Gdyby problem polegał na znalezieniu zmiany, która wymagała najmniejszego kosztu, to naiwny chciwy algorytm, który używałby tyle samo monety o najwyższej wartości, mógłby się nie powieść w przypadku niektórych kombinacji monet i kwoty docelowej. Na przykład, jeśli istnieją monety o wartości 1, 3 i 4; a docelowa kwota to 6, wtedy chciwy algorytm może zasugerować trzy monety o wartości 4, 1 i 1, gdy łatwo jest zauważyć, że można użyć dwóch monet o wartości 3.

  • Paddy.
Paddy3118
źródło
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
źródło
1

Znalazłem ten zgrabny fragment kodu w książce „Python do analizy danych” autorstwa Ooreily. Używa leniwej implementacji i porównania int i przypuszczam, że można go zmodyfikować dla innych nominałów przy użyciu liczb dziesiętnych. Daj mi znać czy to ci pomogło!

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
źródło
1

To jest poprawa odpowiedzi Zihana. Wiele niepotrzebnych pętli pojawia się, gdy nominał wynosi zaledwie 1 cent.

Jest intuicyjny i nierekurencyjny.

    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
źródło
u nie można uogólniać tego rozwiązania, więc na przykład pojawia się nowy element w takim przypadku należy dodać kolejną pętlę for
Sumit Kumar Saha.
1

Proste rozwiązanie 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;
  }
}
GR44
źródło
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
źródło
1

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

Użyj tego w ten sposób:

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

Drukuje:

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
źródło
Wynik jest ładny
dziękuję
1

Poniżej znajduje się program w Pythonie, który pozwala znaleźć wszystkie kombinacje pieniędzy. Jest to rozwiązanie do programowania dynamicznego z czasem zamówienia (n). Pieniądze to 1,5,10,25

Przechodzimy od rzędu pieniędzy 1 do rzędu pieniędzy 25 (4 rzędy). Wiersz pieniądz 1 zawiera liczbę, jeśli weźmiemy pod uwagę tylko pieniądze 1 przy obliczaniu liczby kombinacji. Pieniądze z wiersza 5 tworzą każdą kolumnę, biorąc liczbę w wierszu pieniądze r dla tych samych pieniędzy końcowych plus poprzednie 5 zliczeń w swoim własnym wierszu (bieżąca pozycja minus 5). Pieniądze z rzędu 10 wykorzystują pieniądze z rzędu 5, które zawierają zliczenia dla obu wartości 1,5 i dodają poprzednie 10 zliczeń (bieżąca pozycja minus 10). Pieniądze rzędu 25 wykorzystują pieniądze rzędu 10, które zawierają liczby dla pieniędzy rzędu 1,5,10 plus poprzednie 25 zliczeń.

Na przykład liczby [1] [12] = liczby [0] [12] + liczby [1] [7] (7 = 12-5), co daje 3 = 1 + 2; liczby [3] [12] = liczby [2] [12] + liczby [3] [9] (-13 = 12-25), co daje 4 = 0 + 4, ponieważ -13 to mniej niż 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
źródło
0

Rozwiązanie 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]);

}

}

Niedźwiedź
źródło
0

Poniższe rozwiązanie java, które wydrukuje również różne kombinacje. Łatwy do zrozumienia. Pomysł jest

za sumę 5

Rozwiązaniem jest

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

Jeśli pozostała suma w każdej pętli jest mniejsza niż nominał, tj. Jeśli pozostała suma 1 jest mniejsza niż 2, po prostu przerwij pętlę

Pełny kod poniżej

Proszę mnie poprawić w przypadku jakichkolwiek błędów

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

}

Ojcze Mathew
źródło
0

Oto rozwiązanie oparte na Pythonie, które wykorzystuje rekursję, a także zapamiętywanie, co powoduje złożoność 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
źródło
Okej, wątpię, czy powyższe ma wielomianowy czas działania. Nie jestem pewien, czy w ogóle możemy mieć wielomianowy czas wykonywania. Ale zauważyłem, że powyższa wersja działa szybciej niż wersja niezapamiętana w wielu przypadkach. Będę dalej badał dlaczego
lalatnayak