Jak liczyć możliwych kombinacji dla problemu monety

Question

Próbuję zaimplementować problem monety, specyfikacja Problem jest tak

Tworzenie funkcji policzyć wszystkich możliwych kombinacji monet, które mogą zostać wykorzystane do danej ilości.

All possible combinations for given amount=15, coin types=1 6 7 
1) 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 
2) 1,1,1,1,1,1,1,1,1,6, 
3) 1,1,1,1,1,1,1,1,7, 
4) 1,1,1,6,6, 
5) 1,1,6,7, 
6) 1,7,7, 

prototyp funkcji:

int findCombinationsCount(int amount, int coins[]) 

założyć, że moneta jest posortowana tablica. dla powyższego przykładu funkcja ta powinna powrócić 6.

Ktoś mnie prowadzi, jak to zrealizować?

Answer 1

Można użyć metody funkcji tworzącej dać szybkich algorytmów, które używają liczb zespolonych.

Biorąc pod uwagę wartości monet C1, C2, .., ck, aby uzyskać liczbę sposobów, aby suma n, co potrzebne jest współczynnikiem x^n w

(1 + x^c1 + x^(2c1) + x^(3c1) + ...)(1+x^c2 + x^(2c2) + x^(3c2) + ...)....(1+x^ck + x^(2ck) + x^(3ck) + ...) 

który jest taki sam jak znalezienie współczynnik x^n w

1/(1-x^c1) * 1/(1-x^c2) * ... * (1-x^ck) 

teraz za pomocą zespolonych, x^a - 1 = (x-W1) (x W2) ... (x-wa), w którym W1, W2 etc złożone korzenie jedności.

Tak

1/(1-x^c1) * 1/(1-x^c2) * ... * (1-x^ck) 

można zapisać jako

1/(x-a1)(x-a2)....(x-am) 

, które mogą być zapisane w frakcje częściowych

A1/(x-a1) + A2/(x-a2) + ... + Am/(x-am) 

Współczynnik x^N, w ten można łatwo znaleźć :

A1/(a1)^(n+1) + A2/(a2)^(n+1) + ...+ Am/(am)^(n+1). 

Program komputerowy powinien z łatwością znaleźć Ai i ai (które mogą być liczbami zespolonymi). Oczywiście może to obejmować obliczenia zmiennoprzecinkowe.

Dla dużych n, będzie to prawdopodobnie szybsze niż wyliczenie wszystkich możliwych kombinacji.

Nadzieję, że pomaga.

Answer 2

Użyj rekursji.

int findCombinationsCount(int amount, int coins[]) { 
    return findCombinationsCount(amount, coins, 0); 
} 

int findCombinationsCount(int amount, int coins[], int checkFromIndex) { 
    if (amount == 0) 
     return 1; 
    else if (amount < 0 || coins.length == checkFromIndex) 
     return 0; 
    else { 
     int withFirstCoin = findCombinationsCount(amount-coins[checkFromIndex], coins, checkFromIndex); 
     int withoutFirstCoin = findCombinationsCount(amount, coins, checkFromIndex+1); 
     return withFirstCoin + withoutFirstCoin; 
    } 
} 

Należy jednak sprawdzić tę implementację. Nie mam tutaj Java IDE i jestem trochę zardzewiały, więc może mieć pewne błędy.

Answer 3

rekurencyjna rozwiązaniem może być prawidłowa odpowiedź tutaj:

int findCombinationsCount(int amount, int coins[]) 
{ 
    // I am assuming amount >= 0, coins.length > 0 and all elements of coins > 0. 
    if (coins.length == 1) 
    { 
     return amount % coins[0] == 0 ? 1 : 0; 
    } 
    else 
    { 
     int total = 0; 
     int[] subCoins = arrayOfCoinsExceptTheFirstOne(coins); 
     for (int i = 0 ; i * coins[0] <= amount ; ++i) 
     { 
      total += findCombinationsCount(amount - i * coins[0], subCoins); 
     } 
     return total; 
    } 
} 

Ostrzeżenie: Nie testowałem jeszcze skompilowany lub wyżej.

Answer 4

Pierwszy pomysł:

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

(The „< =” jest zbędne w tym przypadku, ale potrzebne jest bardziej ogólne rozwiązanie, jeśli użytkownik zdecyduje się zmienić swoje parametry)

Answer 5

rekurencyjnego rozwiązania wymienione będą działać, ale będą straszliwie powolne, jeśli dodasz więcej nominałów monet i/lub znacznie zwiększą wartość docelową.

Aby przyspieszyć, należy wdrożyć dynamiczne rozwiązanie programistyczne. Spójrz na knapsack problem. Możesz dostosować wymienione tam rozwiązanie DP, aby rozwiązać problem, utrzymując liczbę sposobów, w jakie można osiągnąć łączną liczbę, a nie minimalną wymaganą liczbę monet.

Answer 6

Ponownie używając rekursji testowanego rozwiązania, choć prawdopodobnie nie jest to najbardziej elegancki kod. (uwaga: zwraca liczbę monet do użycia zamiast powtarzania faktycznej ilości monet n razy).

public class CoinPerm { 


@Test 
public void QuickTest() throws Exception 
{ 
    int ammount = 15; 
    int coins[] = {1,6,7}; 

    ArrayList<solution> solutionList = SolvePerms(ammount, coins); 

    for (solution sol : solutionList) 
    { 
     System.out.println(sol); 
    } 

    assertTrue("Wrong number of solutions " + solutionList.size(),solutionList.size() == 6); 
} 



public ArrayList<solution> SolvePerms(int ammount, int coins[]) throws Exception 
{ 
    ArrayList<solution> solutionList = new ArrayList<solution>(); 
    ArrayList<Integer> emptyList = new ArrayList<Integer>(); 
    solution CurrentSolution = new solution(emptyList); 
    GetPerms(ammount, coins, CurrentSolution, solutionList); 

    return solutionList; 
} 


private void GetPerms(int ammount, int coins[], solution CurrentSolution, ArrayList<solution> mSolutions) throws Exception 
{ 
    int currentCoin = coins[0]; 

    if (currentCoin <= 0) 
    { 
     throw new Exception("Cant cope with negative or zero ammounts"); 
    } 

    if (coins.length == 1) 
    { 
     if (ammount % currentCoin == 0) 
     { 
      CurrentSolution.add(ammount/currentCoin); 
      mSolutions.add(CurrentSolution); 
     } 
     return; 
    } 

    // work out list with one less coin. 
    int coinsDepth = coins.length; 
    int reducedCoins[] = new int[(coinsDepth -1)]; 
    for (int j = 0; j < coinsDepth - 1;j++) 
    { 
     reducedCoins[j] = coins[j+1]; 
    } 


    // integer rounding okay; 
    int numberOfPerms = ammount/currentCoin; 

    for (int j = 0; j <= numberOfPerms; j++) 
    { 
     solution newSolution = CurrentSolution.clone(); 
     newSolution.add(j); 
     GetPerms(ammount - j * currentCoin,reducedCoins, newSolution, mSolutions); 
    } 
} 


private class solution 
{ 
    ArrayList<Integer> mNumberOfCoins; 

    solution(ArrayList<Integer> anumberOfCoins) 
    { 
     mNumberOfCoins = anumberOfCoins; 
    } 

    @Override 
    public String toString() { 
     if (mNumberOfCoins != null && mNumberOfCoins.size() > 0) 
     { 
      String retval = mNumberOfCoins.get(0).toString(); 
      for (int i = 1; i< mNumberOfCoins.size();i++) 
      { 
       retval += ","+mNumberOfCoins.get(i).toString(); 
      } 
      return retval; 
     } 
     else 
     { 
      return ""; 
     } 
    } 

    @Override 
    protected solution clone() 
    { 
     return new solution((ArrayList<Integer>) mNumberOfCoins.clone()); 
    } 

    public void add(int i) { 
     mNumberOfCoins.add(i); 
    } 
} 

}

Answer 7

public static void main(String[] args) { 

    int b,c,total = 15; 
    int combos =1; 
     for(int d=0;d<total/7;d++) 
      { 
      b = total - d * 7; 
      for (int n = 0; n <= b /6; n++) 
     { 
        combos++; 

     } 

     } 

     System.out.print("TOTAL COMBINATIONS = "+combos); 
} 

Answer 8

Chociaż rekurencji może pracować i to często zadanie wdrożyć w niektórych kursach poziomie uczelni na algorytmach & struktur danych, wierzę, że „dynamiczne programowanie” realizacja jest bardziej efektywne.

public static int findCombinationsCount(int sum, int vals[]) { 
     if (sum < 0) { 
      return 0; 
     } 
     if (vals == null || vals.length == 0) { 
      return 0; 
     } 

     int dp[] = new int[sum + 1]; 
     dp[0] = 1; 
     for (int i = 0; i < vals.length; ++i) { 
      for (int j = vals[i]; j <= sum; ++j) { 
       dp[j] += dp[j - vals[i]]; 
      } 
     } 
     return dp[sum]; 
    } 

Answer 9

package algorithms; 

import java.util.Random; 

/**`enter code here` 
* Owner : Ghodrat Naderi 
* E-Mail: Naderi.ghodrat@gmail.com 
* Date : 10/12/12 
* Time : 4:50 PM 
* IDE : IntelliJ IDEA 11 
*/ 
public class CoinProblem 
{ 
    public static void main(String[] args) 
    { 
    int[] coins = {1, 3, 5, 10, 20, 50, 100, 200, 500}; 

    int amount = new Random().nextInt(10000); 
    int coinsCount = 0; 
    System.out.println("amount = " + amount); 
    int[] numberOfCoins = findNumberOfCoins(coins, amount); 
    for (int i = 0; i < numberOfCoins.length; i++) 
    { 
     if (numberOfCoins[i] > 0) 
     { 
     System.out.println("coins= " + coins[i] + " Count=" + numberOfCoins[i] + "\n"); 
     coinsCount += numberOfCoins[i]; 
     } 

    } 
    System.out.println("numberOfCoins = " + coinsCount); 
    } 

    private static int[] findNumberOfCoins(int[] coins, int amount) 
    { 
    int c = coins.length; 
    int[] numberOfCoins = new int[coins.length]; 
    while (amount > 0) 
    { 
     c--; 
     if (amount >= coins[c]) 
     { 
     int quotient = amount/coins[c]; 
     amount = amount - coins[c] * quotient; 
     numberOfCoins[c] = quotient; 
     } 

    } 
    return numberOfCoins; 
    } 
} 

Answer 10

Ten sam problem na monety (1,5,10,25,50) jest jednym z poniższych rozwiązań. Roztwór powinien spełniać równanie: poniżej 1 * a + b + 5 * 10 * 25 * C + D + 50 * e centów ==

publicznego void countWaysToProduceGivenAmountOfMoney (int centów) {

for(int a = 0;a<=cents;a++){ 
     for(int b = 0;b<=cents/5;b++){ 
      for(int c = 0;c<=cents/10;c++){ 
       for(int d = 0;d<=cents/25;d++){ 
        for(int e = 0;e<=cents/50;e++){ 
         if(1*a + 5*b + 10*c + 25*d + 50*e == cents){ 
          System.out.println("1 cents :"+a+", 5 cents:"+b+", 10 cents:"+c); 
         } 
        } 
       } 
      } 
     } 
    } 
} 

Można to zmienić w przypadku ogólnych rozwiązań.

Answer 11

Bardzo prosty z rekursji:

def countChange(money: Int, coins: List[Int]): Int = { 
    def reduce(money: Int, coins: List[Int], accCounter: Int): Int = { 
     if(money == 0) accCounter + 1 
     else if(money < 0 || coins.isEmpty) accCounter 
     else reduce(money - coins.head, coins, accCounter) + reduce(money, coins.tail, accCounter) 
    } 

    if(money <= 0 || coins.isEmpty) 0 
    else reduce(money, coins, 0) 
} 

Jest to przykład w SCALA

Answer 12

Aryabhatta’s answer dla licząc liczbę sposobów, aby zmienić z monet stałych wyznań jest bardzo ładny, ale również niepraktyczne do wdrożenia opisane jako . Zamiast używać liczb zespolonych, użyjemy arytmetyki modularnej , podobnie jak transformata liczbowa zastępująca transformatę Fouriera do mnożenia wielomianów całkowitych.

Niech to jest najczęstsza wielokrotność nominałów monet. Według Twierdzenie Dirichleta o progresjach arytmetycznych istnieje nieskończenie wiele liczb pierwszych p takich, że D dzieli p - 1. (Przy odrobinie szczęścia, , zostaną one nawet rozprowadzone w taki sposób, że będziemy mogli je skutecznie znaleźć.) Wyliczymy liczbę sposobów, w jakie modulo spełni ten warunek. Uzyskując w jakiś sposób surowe wiązanie (np., n + k - 1 wybrać k - 1 gdzie n jest całkowite i k jest liczbą nominałów) powtórzenie tej procedury z różnych bodźce, którego produkt przekracza granicę i zastosowania chiński pozostałą twierdzenie, można odzyskać dokładnej liczby.

Przetestuj kandydatów 1 + k*D dla liczb całkowitych k > 0, dopóki nie znajdziemy liczby pierwszej p. Niech g będzie prymitywnym root modulo p (wygeneruj kandydatów na losowo i zastosuj standardowy test). Dla każdego nominału d wyrażają wielomian x**d - 1 modulo p jako produkt czynników:

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

Należy zauważyć, że d dzieli D dzieli p-1, a więc w rzeczywistości to wykładnik całkowitą.

Niech m będzie sumą denominacji. Zbierz wszystkie stałe g**((p-1)*i/d) jako a(0), ..., a(m-1). Następnym krokiem jest znalezienie ułamki proste A(0), ..., A(m-1) tak, że

sign/product from j=0 to m-1 of (a(j) - x) = 
    sum from j=0 to m-1 of A(j)/(a(j) - x) [modulo p], 

gdzie sign jest 1 jeśli istnieje jeszcze szereg nominałów i -1 jeśli istnieją nieparzysta nominałów. Wyprowadź układ równań liniowych dla A(j), obliczając obie strony danego równania dla różnych wartości x, a następnie rozwiązaj go, eliminując Gaussa . Życie staje się skomplikowane, jeśli istnieją duplikaty; to najprawdopodobniej najłatwiej po prostu wybrać inną liczbę pierwszą.

W tej konfiguracji, możemy obliczyć liczbę sposobów (modulo p, z oczywiście), aby zmiana wysokości n jak

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

Answer 13

Rozwiązanie dostarczone przez @Jordi jest ładny, ale działa bardzo wolno. Możesz wypróbować wejście 600 do tego rozwiązania i zobaczyć, jak powolne.

Mój pomysł polega na wykorzystaniu dynamicznego programowania oddolnego.

Należy zauważyć, że na ogół, możliwe połączenie jakość = M i monet {a, b, c} równa się do

• MC monet {a, b, c} (z monety c)
kombinację
• kombinacja dla mi monet {a, b} (bez monety c).

Jeśli monety nie są dostępne lub dostępne, monety nie mogą pokryć wymaganej kwoty, należy odpowiednio wpisać 0 do bloku. Jeśli kwota wynosi 0, należy wypełnić 1.

public static void main(String[] args){ 
    int[] coins = new int[]{1,2,3,4,5}; 
    int money = 600; 
    int[][] recorder = new int[money+1][coins.length]; 
    for(int k=0;k<coins.length;k++){ 
     recorder[0][k] = 1; 
    } 
    for(int i=1;i<=money;i++){ 
     //System.out.println("working on money="+i); 
     int with = 0; 
     int without = 0; 

     for(int coin_index=0;coin_index<coins.length;coin_index++){ 
      //System.out.println("working on coin until "+coins[coin_index]); 
      if(i-coins[coin_index]<0){ 
       with = 0; 
      }else{ 
       with = recorder[i-coins[coin_index]][coin_index]; 
      } 
      //System.out.println("with="+with); 
      if(coin_index-1<0){ 
       without = 0; 
      }else{ 
       without = recorder[i][coin_index-1]; 
      } 
      //System.out.println("without="+without); 
      //System.out.println("result="+(without+with)); 
      recorder[i][coin_index] = with+without; 
     } 
    } 
    System.out.print(recorder[money][coins.length-1]); 

} 

Answer 14

Poniżej znajduje się rekursja z rozwiązaniem joty do zapamiętania. poniżej mamy 1,2,3,5 jako monety i 200 jako kwotę docelową.

countCombinations(200,new int[]{5,2,3,1} , 0, 0,new Integer[6][200+5]); 

static int countCombinations(Integer targetAmount, int[] V,int currentAmount, int coin, Integer[][] memory){ 

    //Comment below if block if you want to see the perf difference 
    if(memory[coin][currentAmount] != null){ 
     return memory[coin][currentAmount]; 
    } 

    if(currentAmount > targetAmount){ 
     memory[coin][currentAmount] = 0; 
     return 0; 
    } 
    if(currentAmount == targetAmount){ 
     return 1; 
    }  
    int count = 0; 
    for(int selectedCoin : V){ 
     if(selectedCoin >= coin){     
      count += countCombinations(targetAmount, V, currentAmount+selectedCoin, selectedCoin,memory); 
     } 
    }   
    memory[coin][currentAmount] = count;   
    return count; 
}