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

Question

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

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

int findCombinationsCount(int amount, int coins[])

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

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

Answer 1

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

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 здесь, и я немного заржавел, поэтому в нем могут быть некоторые ошибки.

Answer 2

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

Учитывая значения монет 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 и т. Д. - комплексные корни единицы.

So

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 это, вероятно, будет быстрее, чем перечисление всех возможных комбинаций.

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

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

Answer 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

Answer 5

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

Пусть 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, из конечно) внести изменения на сумму n как

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

Answer 6

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 7

Этот код основан на решении, предоставленном JeremyP, которое работает отлично, и я просто улучшил его, чтобы оптимизировать производительность с помощью динамического программирования. Я не смог прокомментировать сообщение JeremyP, потому что у меня недостаточно репутации :)

public static long makeChange(int[] coins, int money) {
    Long[][] resultMap = new Long[coins.length][money+1];
    return getChange(coins,money,0,resultMap);
}

public static long getChange(int[] coins, int money, int index,Long[][] resultMap) {
    if (index == coins.length -1) // if we are at the end      
        return money%coins[index]==0? 1:0;
    else{
        //System.out.printf("Checking index %d and money %d ",index,money);
        Long storedResult =resultMap[index][money];
        if(storedResult != null)
            return storedResult;
        long total=0;
        for(int coff=0; coff * coins[index] <=money; coff ++){

             total += getChange(coins, money - coff*coins[index],index +1,resultMap);
        }
        resultMap[index][money] = total;
        return total;

    }
}

Answer 8

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

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

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

• mc и монет {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]);

}

Answer 9

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

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

Answer 10

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

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

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