Подтвердить что ты не робот

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

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

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

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,

прототип функции:

int findCombinationsCount(int amount, int coins[])

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

Вы можете использовать методы функций генерации, чтобы дать быстрые алгоритмы, которые используют комплексные числа.

Учитывая значения монет c1, c2,..., ck, чтобы получить количество способов суммирования n, вам нужен коэффициент при x ^ n в

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

То же самое, что найти коэффициент при x ^ n в

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

Теперь, используя комплексные числа, x ^ a - 1 = (x-w1) (x-w2)... (x-wa), где w1, w2 и т.д. являются комплексными корнями из единицы.

Итак,

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

может быть записано как

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

которые можно переписать с помощью парциальных дробей,

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

Коэффициент при x ^ n в этом легко найти:

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

Компьютерная программа должна легко находить Ai и ai (которые могут быть сложными числами). Конечно, это может включать вычисления с плавающей запятой.

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

Надеюсь, что это поможет.

Ответ 2

Используйте рекурсию.

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

Однако вы должны проверить эту реализацию. У меня нет Java IDE здесь, и я немного ржавый, поэтому у него могут быть некоторые ошибки.

Ответ 3

Хотя рекурсия может работать и часто является назначением для реализации на некоторых курсах уровня колледжа по алгоритмам и структурам данных, я считаю, что реализация "динамического программирования" более эффективна.

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

Ответ 4

Очень просто с рекурсией:

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

Это пример в SCALA

Ответ 5

Ответ Aryabhattas для подсчитывая количество способов внесения изменений с монетами фиксированного деноминации очень симпатичны, но также нецелесообразно реализовать в качестве описано. Вместо использования комплексных чисел, используйте модульную арифметика, подобно тому, как теоретико-числовое преобразование заменяет Преобразование Фурье для умножения целочисленных многочленов.

Пусть D будет наименьшим общим кратным наименований монет. От Теорема Дирихле об арифметических прогрессиях существует бесконечно много простых чисел p таких, что D делит p - 1. (В любом случае, они даже будут распределены таким образом, что мы сможем их найти эффективно.) Хорошо вычислите количество способов по модулю p удовлетворяющих этому условию. Получая грубую привязку каким-либо образом (например, n + k - 1 выберите k - 1, где n - это сумма, а k - число деноминаций), повторяя эту процедуру несколькими штрихи, продукт которых превышает эту границу, и применяя китайские теоремы останова, мы можем восстановить точное число.

Проверите кандидатов 1 + k*D для целых чисел k > 0, пока мы не найдем простой p. Пусть g - примитивный корень по модулю p (сгенерируйте кандидатов в случайный и применить стандартный тест). Для каждого наименования D, выражаем полином x**d - 1 по модулю p как произведение факторов:

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

Обратите внимание, что D делит D делит p-1, поэтому показатель действительно является целое число.

Пусть m - сумма наименований. Соберите все константы g**((p-1)*i/d) как a(0), ..., a(m-1). Следующий шаг - найти разбиение частичной части a(0), ..., a(m-1) такое, что

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

где sign есть 1, если существует четное число наименований и -1, если существует нечетное число наименований. Выведите систему линейных уравнений для A(j) путем оценки обеих сторон данного уравнение для разных значений x, затем решить его с помощью гауссовского устранение. Жизнь усложняется, если есть дубликаты; возможно, проще всего выбрать другое простое.

Учитывая эту настройку, мы можем вычислить количество способов (по модулю p, of курс), чтобы внести изменения в n как

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

Ответ 6

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

Ответ 7

Рекурсивное решение может быть правильным ответом здесь:

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

Предупреждение: я не тестировал или даже не компилировал выше.

Ответ 8

Рекурсивные решения, упомянутые, будут работать, но они будут ужасно медленными, если вы добавите больше номиналов монет и/или значительно увеличите целевое значение.

Что нужно, чтобы ускорить его, - это реализовать решение динамического программирования. Посмотрите на проблему рюкзак. Вы можете адаптировать решение DP, упомянутое здесь, чтобы решить вашу проблему, сохранив количество возможных способов достижения общего количества, а не минимальное количество требуемых монет.

Ответ 9

Решение, предоставляемое @Jordi, приятно, но работает очень медленно. Вы можете попробовать вход 600 в это решение и посмотреть, насколько он медленный.

Моя идея - использовать динамическое программирование снизу вверх.

Заметим, что в общем случае возможная комбинация для денег = m и монеты {a, b, c} равна комбинации для

  • m-c и монеты {a, b, c} (с монетой c)
  • комбинация для m и монет {a, b} (без монетки c).

Если монеты не доступны или доступны, монеты не могут покрыть требуемую сумму денег, она должна соответственно заполнить 0 до блока. Если сумма денег равна 0, она должна заполнить 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]);

}

Ответ 10

Первая идея:

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

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

Ответ 11

Опять же, используя рекурсию, проверенное решение, хотя, вероятно, не самый элегантный код. (обратите внимание, что он возвращает количество использованной монеты, а не повторяет фактическое количество монеты 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);
    }
}

}

Ответ 12

Ниже приведена рекурсия с помощью java-решения memoization. для ниже одного мы имеем 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;
}

Ответ 13

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

Ответ 14

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

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

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