Как рассчитать возможную комбинацию для проблемы с монетами

Question

Я пытаюсь реализовать проблему с монетами, спецификация проблемы выглядит следующим образом

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

int findCombinationsCount(int amount, int coins[])

Предположим, что массив монет отсортирован.для приведенного выше примера эта функция должна возвращать 6.

Кто-нибудь подскажет, как реализовать это ??

Answer 1

Ниже приведена рекурсия с Java-решением для памятки. ниже одного у нас есть 1,2,3,5 в качестве монет и 200 в качестве целевой суммы.

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 2

Та же задача для монет (1,5,10,25,50) имеет одно из следующих решений.Решение должно удовлетворять следующему уравнению: 1 * a + 5 * b + 10 * c + 25 * d + 50 * e == центов

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

Это можно изменить для любых общих решений.

Answer 3

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 4

Опять рекурсия - проверенное решение, хотя, возможно, не самый элегантный код. (обратите внимание, что возвращается номер каждой используемой монеты, а не повторяется фактическое количество монет n раз).

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 5

Первая идея:

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

(в этом случае '<=' является излишним, но необходимо для более общего решения, если вы решите изменить свои параметры) </p>