java - programa - Cómo contar posible combinación para el problema de la moneda

programa para dar cambio dinero

Question

Estoy tratando de implementar un problema de monedas, la especificación del problema es así

Crea una función para contar todas las combinaciones posibles de monedas que se pueden usar para la cantidad dada.

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,

prototipo de función:

int findCombinationsCount(int amount, int coins[])

supongamos que la matriz de monedas está ordenada. para el ejemplo anterior, esta función debería devolver 6.

¿Alguien me guía cómo implementar esto?

Answer 1

Aunque la recursión puede funcionar y es a menudo una tarea para implementar en algunos cursos de nivel universitario sobre Algoritmos y Estructuras de Datos, creo que la implementación de "programación dinámica" es más eficiente.

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 2

De nuevo, utilizando recursion una solución probada, aunque probablemente no sea el código más elegante. (tenga en cuenta que devuelve el número de cada moneda para usar en lugar de repetir la cantidad real de monedas n veces).

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 3

Primera idea:

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

(el ''<='' es superfluo en este caso, pero es necesario para una solución más general, si decide cambiar sus parámetros)

Answer 4

Puede usar métodos de función de generación para proporcionar algoritmos rápidos, que usan números complejos.

Dados los valores de moneda c1, c2, ..., ck, para obtener el número de formas de sumar n, lo que necesita es el coeficiente de x ^ n en

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

Lo cual es lo mismo que encontrar el coeficiente de x ^ n en

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

Ahora usando números complejos, x ^ a - 1 = (x-w1) (x-w2) ... (x-wa) donde w1, w2, etc. son las raíces complejas de la unidad.

Asi que

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

Se puede escribir como

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

que puede ser reescrito usando fracciones parciales son

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

El coeficiente de x ^ n en esto se puede encontrar fácilmente:

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

Un programa de computadora debería ser capaz de encontrar fácilmente Ai y ai (que podrían ser números complejos). Por supuesto, esto podría implicar cálculos en coma flotante.

Para n grande, probablemente sea más rápido que enumerar todas las combinaciones posibles.

Espero que ayude.

Answer 5

Una solución recursiva podría ser la respuesta correcta aquí:

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

Advertencia: no he probado ni compilado lo anterior.

Answer 6

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 7

Las soluciones recursivas mencionadas funcionarán, pero van a ser tremendamente lentas si agrega más denominaciones de monedas y / o aumenta el valor objetivo significativamente.

Lo que necesita para acelerarlo es implementar una solución de programación dinámica. Eche un vistazo al problema de la mochila . Puede adaptar la solución de DP mencionada allí para resolver su problema contando la cantidad de formas en que puede alcanzarse un total en lugar de la cantidad mínima de monedas requerida.

Answer 8

package algorithms;

import java.util.Random;

/**`enter code here`
 * Owner : Ghodrat Naderi
 * E-Mail: [email protected]
 * 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 9

El mismo problema para las monedas (1,5,10,25,50) tiene una de las siguientes soluciones. La solución debe cumplir la ecuación siguiente: 1 * a + 5 * b + 10 * c + 25 * d + 50 * e == centavos

public static void countWaysToProduceGivenAmountOfMoney (int cents) {

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

Esto puede modificarse para cualquier solución general.

Answer 10

Use recursión.

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

Sin embargo, debes verificar esta implementación. No tengo un IDE de Java aquí, y estoy un poco oxidado, por lo que puede haber algunos errores.

Answer 11

Muy simple con recursividad:

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

Este es un ejemplo en SCALA

Answer 12

La solución proporcionada por @Jordi es agradable, pero funciona extremadamente lento. Puedes probar la entrada 600 a esa solución y ver qué tan lenta es.

Mi idea es usar programación dinámica ascendente.

Tenga en cuenta que, en general, la combinación posible de dinero = m y monedas {a, b, c} es igual a la combinación para

• mc y monedas {a, b, c} (con moneda c)
• combinación para m y monedas {a, b} (sin moneda c).

Si no hay monedas disponibles o las monedas disponibles no pueden cubrir la cantidad de dinero requerida, debe completar 0 en el bloque en consecuencia. Si la cantidad de dinero es 0, debe completar 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 13

A continuación se muestra la recursión con la solución de memoria de java. para debajo de uno tenemos 1,2,3,5 como monedas y 200 como cantidad objetivo.

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

Answer 14

La respuesta de Aryabhatta para contar el número de formas de hacer cambios con monedas de denominaciones fijas es muy bonita pero tampoco es práctica de implementar como se describe. En lugar de utilizar números complejos, utilizaremos aritmética modular, similar a cómo la transformación teórica de números reemplaza a una transformada de Fourier para multiplicar polinomios enteros.

Deje D ser el mínimo común múltiplo de las denominaciones de moneda. Según el teorema de Dirichlet sobre progresiones aritméticas, existen infinitos números primos p tales que D divide p - 1 . (Con un poco de suerte, incluso se distribuirán de manera tal que podamos encontrarlos de manera eficiente.) Calcularemos el número de maneras en que un módulo satisface esta condición. Obteniendo un límite bruto de alguna manera (por ejemplo, n + k - 1 elije k - 1 donde n es el total k es el número de denominaciones), repitiendo este procedimiento con varios primos diferentes cuyo producto excede ese límite, y aplicando el resto chino Teorema, podemos recuperar el número exacto.

Pruebe los candidatos 1 + k*D para los enteros k > 0 hasta que encontremos un primo p . Deje g ser un módulo de raíz primitiva p (generar candidatos al azar y aplicar la prueba estándar). Para cada denominación d , exprese el polinomio x**d - 1 módulo p como producto de factores:

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

Tenga en cuenta que d divide D divide p-1 , por lo que el exponente es un número entero.

Deje m ser la suma de las denominaciones. Reúna todas las constantes g**((p-1)*i/d) como a(0), ..., a(m-1) . El siguiente paso es encontrar una descomposición de fracción parcial A(0), ..., A(m-1) tal que

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],

donde el sign es 1 si hay un número par de denominaciones y -1 si hay un número impar de denominaciones. Derive un sistema de ecuaciones lineales para A(j) evaluando ambos lados de la ecuación dada para diferentes valores de x , luego resuélvalo con eliminación gaussiana. La vida se complica si hay duplicados; Probablemente sea más fácil simplemente elegir otro primo.

Dada esta configuración, podemos calcular el número de formas (módulo p , por supuesto) para hacer que el cambio sea n

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