Как найти все комбинации монет при некоторой долларовой стоимости

114

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

Согласно моему комментарию, он пытался решить эту проблему:

Учитывая некоторую долларовую стоимость в центах (например, 200 = 2 доллара, 1000 = 10 долларов), найдите все комбинации монет, которые составляют долларовую стоимость. Разрешены только пенни (1 цент), никель (5 центов), десять центов (10 центов) и четвертинки (25 центов).

Например, если дано 100, ответ должен быть таким:

4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies  
3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies  
etc.

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

codingbear
источник
6
@akappa: пенни = 1 цент; никель = 5 центов; дайм = 10 центов; четверть = 25 центов :)
codingbear 09
@John T: код для гольфа? Я никогда не слышал об этом термине! В любом случае, я надеюсь увидеть несколько интересных ответов, поскольку сообщество SO может решить любую проблему
codingbear
Я также постараюсь опубликовать свой ответ, когда вернусь домой ... все еще на работе, и мне не следует тратить слишком много времени на SO.
codingbear 09
1
Код @blee гольф относится к решению проблемы с наименьшим возможным количеством символов, с помощью языка программирования по вашему выбору. Вот некоторые из того, что было сделано на этом веб-сайте: stackoverflow.com/search?q=code+golf
Джон Т.
1
code-golf=> stackoverflow.com/questions/tagged/code-golf
Брэд Гилберт

Ответы:

54

Я изучал это однажды, давным-давно, и вы можете прочитать мою небольшую рецензию на это . Вот исходный код Mathematica .

Используя производящие функции, вы можете получить решение проблемы в закрытом виде с постоянным временем. Книга Грэма, Кнута и Паташника « Конкретная математика» предназначена для этого и содержит довольно обширное обсуждение проблемы. По сути, вы определяете многочлен, где n- й коэффициент - это количество способов внести сдачу на n долларов.

На страницах 4–5 описания показано, как с помощью Mathematica (или любой другой удобной системы компьютерной алгебры) вычислить ответ на сумму 10 ^ 10 ^ 6 долларов за пару секунд в трех строках кода.

(И это было достаточно давно, это пара секунд на Pentium 75 МГц ...)

andrewdotn
источник
16
Хороший ответ, но небольшие придирки: обратите внимание, что (1) это дает количество способов, в то время как по какой-то причине вопрос задает фактический набор всех способов. Конечно, не может быть никакого способа найти набор за полиномиальное время, так как сам результат имеет суперполиномиальное количество записей (2). Спорный вопрос, является ли производящая функция «замкнутой формой» (см. Замечательную книгу Герберта Уилфа Generatingfunctionology : math. upenn.edu/~wilf/DownldGF.html ), и если вы имеете в виду такое выражение, как (1 + √5) ^ n, для вычисления требуется время Ω (log n), а не постоянное время.
ShreevatsaR
Мягкое введение в динамическое программирование. Кроме того, я рекомендую всем, у кого есть проблемы с последовательностью, прочитать генерирующую функциональность .
Colonel Panic
Большое спасибо, Эндрю ... это объяснение очень помогло мне ... Публикация функции scala ниже ... если она кому-то понадобится
jayaram S
1
Я считаю, что вопрос вначале нуждается в небольшой корректировке, потому что он спрашивает: «... используя монеты номиналом 1, 10, 25, 50 и 100 центов?» Но затем запись определяет набор aкак область « fно» a = {1,5,10,25,50,100}. В списке монет должна быть 5 центов. В противном случае описание было фантастическим, спасибо!
rbrtl
@rbrtl Вау, вы правы, спасибо, что заметили это! Я
обновлю
42

Примечание . Здесь показано только количество способов.

Функция Scala:

def countChange(money: Int, coins: List[Int]): Int =
  if (money == 0) 1
  else if (coins.isEmpty || money < 0) 0
  else countChange(money - coins.head, coins) + countChange(money, coins.tail)
Влад
источник
1
Есть ли действительно один способ изменить 0? Думаю, этого нет.
Люк
2
Это связано с количеством полиномиальных решений n1 * coins(0) + n2 * coins(1) + ... + nN * coins(N-1) = money. Таким образом, для money=0и coins=List(1,2,5,10)количество комбинаций (n1, n2, n3, n4)равно 1, а решение равно (0, 0, 0, 0).
Кир
3
Я не могу понять, почему эта реализация работает. Может кто-нибудь объяснить мне алгоритм?
Adrien Lemaire
3
Это определенно точный ответ на проблему 3 упражнения 1 курса coursera scala.
Джастин Стандарт
Я считаю, что, если, money == 0но coins.isEmpty, это не должно считаться солнцем. Следовательно, алгоритм может быть лучше обслужен, если coins.isEmpty || money < 0сначала выполняется проверка условия.
juanchito
26

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

В основном вы переходите от самого большого к наименьшему номиналу.
Рекурсивный,

  1. У вас есть текущая сумма, которую нужно заполнить, и наибольший номинал (осталось более 1). Если остался только 1 номинал, есть только один способ заполнить общую сумму. Вы можете использовать от 0 до k копий вашего текущего номинала, так что k * cur denomination <= total.
  2. Для значений от 0 до k вызовите функцию с измененным общим значением и новым наибольшим номиналом.
  3. Сложите результаты от 0 до k. Вот сколько способов вы можете заполнить свою сумму, начиная с текущего номинала. Верните этот номер.

Вот моя версия вашей заявленной проблемы на Python за 200 центов. Получаю 1463 способа. В этой версии печатаются все комбинации и итоговая сумма.

#!/usr/bin/python

# find the number of ways to reach a total with the given number of combinations

cents = 200
denominations = [25, 10, 5, 1]
names = {25: "quarter(s)", 10: "dime(s)", 5 : "nickel(s)", 1 : "pennies"}

def count_combs(left, i, comb, add):
    if add: comb.append(add)
    if left == 0 or (i+1) == len(denominations):
        if (i+1) == len(denominations) and left > 0:
           if left % denominations[i]:
               return 0
           comb.append( (left/denominations[i], demoninations[i]) )
           i += 1
        while i < len(denominations):
            comb.append( (0, denominations[i]) )
            i += 1
        print(" ".join("%d %s" % (n,names[c]) for (n,c) in comb))
        return 1
    cur = denominations[i]
    return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))

count_combs(cents, 0, [], None)
Лейф
источник
Я не запускал его, но, если
проанализировать
Вы можете заменить последние две строки функции на «return sum (count_combs (...) for ...)» - таким образом список вообще не будет материализован. :)
Ник Джонсон
Спасибо за чаевые. Меня всегда интересуют способы ужесточить код.
leif
2
Как обсуждалось в другом вопросе , этот код будет давать неправильный вывод, если в списке denominationsнет 1последнего значения. Вы можете добавить небольшой объем кода во внутренний ifблок, чтобы исправить это (как я описываю в своем ответе на другой вопрос).
Blckknght
12

Функция Scala:

def countChange(money: Int, coins: List[Int]): Int = {

def loop(money: Int, lcoins: List[Int], count: Int): Int = {
  // if there are no more coins or if we run out of money ... return 0 
  if ( lcoins.isEmpty || money < 0) 0
  else{
    if (money == 0 ) count + 1   
/* if the recursive subtraction leads to 0 money left - a prefect division hence return count +1 */
    else
/* keep iterating ... sum over money and the rest of the coins and money - the first item and the full set of coins left*/
      loop(money, lcoins.tail,count) + loop(money - lcoins.head,lcoins, count)
  }
}

val x = loop(money, coins, 0)
Console println x
x
}
jayaram S
источник
Спасибо! Это отличное начало. Но я думаю, что это не работает, когда «деньги» начинаются с 0 :).
aqn
10

Вот какой-то абсолютно простой код на C ++ для решения проблемы, который требует, чтобы были показаны все комбинации.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        printf("usage: change amount-in-cents\n");
        return 1;
    }

    int total = atoi(argv[1]);

    printf("quarter\tdime\tnickle\tpenny\tto make %d\n", total);

    int combos = 0;

    for (int q = 0; q <= total / 25; q++)
    {
        int total_less_q = total - q * 25;
        for (int d = 0; d <= total_less_q / 10; d++)
        {
            int total_less_q_d = total_less_q - d * 10;
            for (int n = 0; n <= total_less_q_d / 5; n++)
            {
                int p = total_less_q_d - n * 5;
                printf("%d\t%d\t%d\t%d\n", q, d, n, p);
                combos++;
            }
        }
    }

    printf("%d combinations\n", combos);

    return 0;
}

Но меня очень заинтриговала подзадача - просто подсчет количества комбинаций. Я подозреваю, что для этого есть уравнение в закрытой форме.

Джордж Филлипс
источник
9
Конечно, это C, а не C ++.
nikhil
1
@ Джордж Филлипс, ты можешь объяснить?
Примерка
Я думаю, это довольно просто. По сути, идея состоит в том, чтобы перебрать все четверти (используя 0,1,2 .. макс.), А затем перебрать все десятицентовики на основе используемых четвертей и т. Д.
Питер Ли
4
Обратной стороной этого решения является: если есть монеты номиналом 50, 100 и 500 центов, тогда мы должны использовать 6-уровневые петли ...
Питер Ли
3
Это очень плохо, если у вас есть динамические купюры или вы хотите добавить другой номинал, тогда это не сработает.
shinzou
7

Подзадача - типичная проблема динамического программирования.

/* Q: Given some dollar value in cents (e.g. 200 = 2 dollars, 1000 = 10 dollars),
      find the number of combinations of coins that make up the dollar value.
      There are only penny, nickel, dime, and quarter.
      (quarter = 25 cents, dime = 10 cents, nickel = 5 cents, penny = 1 cent) */
/* A:
Reference: http://andrew.neitsch.ca/publications/m496pres1.nb.pdf
f(n, k): number of ways of making change for n cents, using only the first
         k+1 types of coins.

          +- 0,                        n < 0 || k < 0
f(n, k) = |- 1,                        n == 0
          +- f(n, k-1) + f(n-C[k], k), else
 */

#include <iostream>
#include <vector>
using namespace std;

int C[] = {1, 5, 10, 25};

// Recursive: very slow, O(2^n)
int f(int n, int k)
{
    if (n < 0 || k < 0)
        return 0;

    if (n == 0)
        return 1;

    return f(n, k-1) + f(n-C[k], k); 
}

// Non-recursive: fast, but still O(nk)
int f_NonRec(int n, int k)
{
    vector<vector<int> > table(n+1, vector<int>(k+1, 1));

    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= k; ++j)
        {
            if (i < 0 || j < 0) // Impossible, for illustration purpose
            {
                table[i][j] = 0;
            }
            else if (i == 0 || j == 0) // Very Important
            {
                table[i][j] = 1;
            }
            else
            {
                // The recursion. Be careful with the vector boundary
                table[i][j] = table[i][j-1] + 
                    (i < C[j] ? 0 : table[i-C[j]][j]);
            }
        }
    }

    return table[n][k];
}

int main()
{
    cout << f(100, 3) << ", " << f_NonRec(100, 3) << endl;
    cout << f(200, 3) << ", " << f_NonRec(200, 3) << endl;
    cout << f(1000, 3) << ", " << f_NonRec(1000, 3) << endl;

    return 0;
}
Питер Ли
источник
Ваши динамические решения требуют, чтобы длина k была равна C минус 1. Это немного сбивает с толку. Вы можете легко изменить его, чтобы поддерживать реальную длину C.
Идан
7

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

public class RepresentCents {

    public static int sum(int n) {

        int count = 0;
        for (int i = 0; i <= n / 25; i++) {
            for (int j = 0; j <= n / 10; j++) {
                for (int k = 0; k <= n / 5; k++) {
                    for (int l = 0; l <= n; l++) {
                        int v = i * 25 + j * 10 + k * 5 + l;
                        if (v == n) {
                            count++;
                        } else if (v > n) {
                            break;
                        }
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(sum(100));
    }
}
Zihan
источник
7

Это действительно старый вопрос, но я придумал рекурсивное решение на java, которое казалось меньше, чем все другие, так что вот -

 public static void printAll(int ind, int[] denom,int N,int[] vals){
    if(N==0){
        System.out.println(Arrays.toString(vals));
        return;
    }
    if(ind == (denom.length))return;             
    int currdenom = denom[ind];
    for(int i=0;i<=(N/currdenom);i++){
        vals[ind] = i;
        printAll(ind+1,denom,N-i*currdenom,vals);
    }
 }

Улучшения:

  public static void printAllCents(int ind, int[] denom,int N,int[] vals){
        if(N==0){
            if(ind < denom.length) {
                for(int i=ind;i<denom.length;i++)
                    vals[i] = 0;
            }
            System.out.println(Arrays.toString(vals));
            return;
        }
        if(ind == (denom.length)) {
            vals[ind-1] = 0;
            return;             
        }

        int currdenom = denom[ind];
        for(int i=0;i<=(N/currdenom);i++){ 
                vals[ind] = i;
                printAllCents(ind+1,denom,N-i*currdenom,vals);
        }
     }
Рохит Пандей
источник
6

Пусть C (i, J) набор комбинаций получения i центов с использованием значений из множества J.

Вы можете определить C так:

введите описание изображения здесь

(сначала (J) детерминированно принимает элемент множества)

Получается довольно рекурсивная функция ... и достаточно эффективная, если вы используете мемоизацию;)

akappa
источник
Да, это (в некотором смысле «динамическое программирование») будет оптимальным решением.
ShreevatsaR 09
вы правы: возьмите J как список, а не как набор: тогда first (J) приносит вам первый элемент, а J \ first (J) дает вам остальную часть списка.
akappa 09
что это за математика?
Мухаммад Умер
5

полувак, чтобы обойти проблему уникальной комбинации - принудительный порядок убывания:

$ деномс = [1,5,10,25]
def all_combs (сумма, последняя) 
  вернуть 1, если сумма == 0
  return $ denoms.select {| d | d & le сумма && d & le last} .inject (0) {| total, denom |
           всего + all_combs (сумма-DENOM, DENOM)}
конец

Это будет работать медленно, поскольку оно не будет запоминаться, но идею вы поняли.

klochner
источник
4
# short and sweet with O(n) table memory    

#include <iostream>
#include <vector>

int count( std::vector<int> s, int n )
{
  std::vector<int> table(n+1,0);

  table[0] = 1;
  for ( auto& k : s )
    for(int j=k; j<=n; ++j)
      table[j] += table[j-k];

  return table[n];
}

int main()
{
  std::cout <<  count({25, 10, 5, 1}, 100) << std::endl;
  return 0;
}
оборота bjackfly
источник
3

Это мой ответ на Python. Он не использует рекурсию:

def crossprod (list1, list2):
    output = 0
    for i in range(0,len(list1)):
        output += list1[i]*list2[i]

    return output

def breakit(target, coins):
    coinslimit = [(target / coins[i]) for i in range(0,len(coins))]
    count = 0
    temp = []
    for i in range(0,len(coins)):
        temp.append([j for j in range(0,coinslimit[i]+1)])


    r=[[]]
    for x in temp:
        t = []
        for y in x:
            for i in r:
                t.append(i+[y])
        r = t

    for targets in r:
        if crossprod(targets, coins) == target:
            print targets
            count +=1
    return count




if __name__ == "__main__":
    coins = [25,10,5,1]
    target = 78
    print breakit(target, coins)

Пример вывода

    ...
    1 ( 10 cents)  2 ( 5 cents)  58 ( 1 cents)  
    4 ( 5 cents)  58 ( 1 cents)  
    1 ( 10 cents)  1 ( 5 cents)  63 ( 1 cents)  
    3 ( 5 cents)  63 ( 1 cents)  
    1 ( 10 cents)  68 ( 1 cents)  
    2 ( 5 cents)  68 ( 1 cents)  
    1 ( 5 cents)  73 ( 1 cents)  
    78 ( 1 cents)  
    Number of solutions =  121
отметка
источник
3
var countChange = function (money,coins) {
  function countChangeSub(money,coins,n) {
    if(money==0) return 1;
    if(money<0 || coins.length ==n) return 0;
    return countChangeSub(money-coins[n],coins,n) + countChangeSub(money,coins,n+1);
  }
  return countChangeSub(money,coins,0);
}
jasonhao
источник
2

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

DJNA
источник
2

Если это позволяет валютная система, простой жадный алгоритм который берет как можно больше каждой монеты, начиная с валюты самой высокой стоимости.

В противном случае требуется динамическое программирование, чтобы быстро найти оптимальное решение, поскольку эта проблема, по сути, является проблемой ранца .

Например, если в валютной системе есть монеты:, {13, 8, 1}жадное решение внесет изменение на 24 as {13, 8, 1, 1, 1}, но истинное оптимальное решение -{8, 8, 8}

Изменить: я думал, что мы вносим изменения оптимально, не перечисляя все способы внести изменения за доллар. В моем недавнем интервью меня спрашивали, как внести изменения, поэтому я сразу перескочил вперед, чтобы прочитать вопрос.

Бен С
источник
проблема не обязательно в одном долларе - это может быть 2 или 23, так что ваше решение остается единственно правильным.
Neil G
2

Я знаю, что это очень старый вопрос. Я искал правильный ответ и не смог найти ничего простого и удовлетворительного. Мне потребовалось некоторое время, но я смог кое-что записать.

function denomination(coins, original_amount){
    var original_amount = original_amount;
    var original_best = [ ];

    for(var i=0;i<coins.length; i++){
      var amount = original_amount;
      var best = [ ];
      var tempBest = [ ]
      while(coins[i]<=amount){
        amount = amount - coins[i];
        best.push(coins[i]);
      }
      if(amount>0 && coins.length>1){
        tempBest = denomination(coins.slice(0,i).concat(coins.slice(i+1,coins.length)), amount);
        //best = best.concat(denomination(coins.splice(i,1), amount));
      }
      if(tempBest.length!=0 || (best.length!=0 && amount==0)){
        best = best.concat(tempBest);
        if(original_best.length==0 ){
          original_best = best
        }else if(original_best.length > best.length ){
          original_best = best;
        }  
      }
    }
    return original_best;  
  }
  denomination( [1,10,3,9] , 19 );

Это решение на javascript, использующее рекурсию.

Варуна
источник
Это решение находит только один номинал. Вопрос был в том, чтобы найти «все» деноминации.
heinob
2

На языке программирования Scala я бы сделал это так:

 def countChange(money: Int, coins: List[Int]): Int = {

       money match {
           case 0 => 1
           case x if x < 0 => 0
           case x if x >= 1 && coins.isEmpty => 0
           case _ => countChange(money, coins.tail) + countChange(money - coins.head, coins)

       }

  }
MrOnyancha
источник
2

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

var bills = new int[] { 100, 50, 20, 10, 5, 1 };

void PrintAllWaysToMakeChange(int sumSoFar, int minBill, string changeSoFar)
{
    for (int i = minBill; i < bills.Length; i++)
    {
        var change = changeSoFar;
        var sum = sumSoFar;

        while (sum > 0)
        {
            if (!string.IsNullOrEmpty(change)) change += " + ";
            change += bills[i];

            sum -= bills[i]; 
            if (sum > 0)
            {
                PrintAllWaysToMakeChange(sum, i + 1, change);
            }
        }

        if (sum == 0)
        {
            Console.WriteLine(change);
        }
    }
}

PrintAllWaysToMakeChange(15, 0, "");

Печатает следующее:

10 + 5
10 + 1 + 1 + 1 + 1 + 1
5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
5 + 5 + 1 + 1 + 1 + 1 + 1
5 + 5 + 5
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
оборота пользователь 7431997
источник
1

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

// Generate a pretty string
val coinNames = List(("quarter", "quarters"), 
                     ("dime", "dimes"), 
                     ("nickel", "nickels"), 
                     ("penny", "pennies"))
def coinsString = 
  Function.tupled((quarters: Int, dimes: Int, nickels:Int, pennies: Int) => (
    List(quarters, dimes, nickels, pennies) 
    zip coinNames // join with names
    map (t => (if (t._1 != 1) (t._1, t._2._2) else (t._1, t._2._1))) // correct for number
    map (t => t._1 + " " + t._2) // qty name
    mkString " "
  ))

def allCombinations(amount: Int) = 
 (for{quarters <- 0 to (amount / 25)
      dimes <- 0 to ((amount - 25*quarters) / 10)
      nickels <- 0 to ((amount - 25*quarters - 10*dimes) / 5)
  } yield (quarters, dimes, nickels, amount - 25*quarters - 10*dimes - 5*nickels)
 ) map coinsString mkString "\n"

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

// Just to make things a bit more readable, as these routines will access
// arrays a lot
val coinValues = List(25, 10, 5, 1)
val coinNames = List(("quarter", "quarters"), 
                     ("dime", "dimes"), 
                     ("nickel", "nickels"), 
                     ("penny", "pennies"))
val List(quarter, dime, nickel, penny) = coinValues.indices.toList


// Find the combination that uses the least amount of coins
def leastCoins(amount: Int): Array[Int] =
  ((List(amount) /: coinValues) {(list, coinValue) =>
    val currentAmount = list.head
    val numberOfCoins = currentAmount / coinValue
    val remainingAmount = currentAmount % coinValue
    remainingAmount :: numberOfCoins :: list.tail
  }).tail.reverse.toArray

// Helper function. Adjust a certain amount of coins by
// adding or subtracting coins of each type; this could
// be made to receive a list of adjustments, but for so
// few types of coins, it's not worth it.
def adjust(base: Array[Int], 
           quarters: Int, 
           dimes: Int, 
           nickels: Int, 
           pennies: Int): Array[Int] =
  Array(base(quarter) + quarters, 
        base(dime) + dimes, 
        base(nickel) + nickels, 
        base(penny) + pennies)

// We decrease the amount of quarters by one this way
def decreaseQuarter(base: Array[Int]): Array[Int] =
  adjust(base, -1, +2, +1, 0)

// Dimes are decreased this way
def decreaseDime(base: Array[Int]): Array[Int] =
  adjust(base, 0, -1, +2, 0)

// And here is how we decrease Nickels
def decreaseNickel(base: Array[Int]): Array[Int] =
  adjust(base, 0, 0, -1, +5)

// This will help us find the proper decrease function
val decrease = Map(quarter -> decreaseQuarter _,
                   dime -> decreaseDime _,
                   nickel -> decreaseNickel _)

// Given a base amount of coins of each type, and the type of coin,
// we'll produce a list of coin amounts for each quantity of that particular
// coin type, up to the "base" amount
def coinSpan(base: Array[Int], whichCoin: Int) = 
  (List(base) /: (0 until base(whichCoin)).toList) { (list, _) =>
    decrease(whichCoin)(list.head) :: list
  }

// Generate a pretty string
def coinsString(base: Array[Int]) = (
  base 
  zip coinNames // join with names
  map (t => (if (t._1 != 1) (t._1, t._2._2) else (t._1, t._2._1))) // correct for number
  map (t => t._1 + " " + t._2)
  mkString " "
)

// So, get a base amount, compute a list for all quarters variations of that base,
// then, for each combination, compute all variations of dimes, and then repeat
// for all variations of nickels.
def allCombinations(amount: Int) = {
  val base = leastCoins(amount)
  val allQuarters = coinSpan(base, quarter)
  val allDimes = allQuarters flatMap (base => coinSpan(base, dime))
  val allNickels = allDimes flatMap (base => coinSpan(base, nickel))
  allNickels map coinsString mkString "\n"
}

Итак, для 37 монет, например:

scala> println(allCombinations(37))
0 quarter 0 dimes 0 nickels 37 pennies
0 quarter 0 dimes 1 nickel 32 pennies
0 quarter 0 dimes 2 nickels 27 pennies
0 quarter 0 dimes 3 nickels 22 pennies
0 quarter 0 dimes 4 nickels 17 pennies
0 quarter 0 dimes 5 nickels 12 pennies
0 quarter 0 dimes 6 nickels 7 pennies
0 quarter 0 dimes 7 nickels 2 pennies
0 quarter 1 dime 0 nickels 27 pennies
0 quarter 1 dime 1 nickel 22 pennies
0 quarter 1 dime 2 nickels 17 pennies
0 quarter 1 dime 3 nickels 12 pennies
0 quarter 1 dime 4 nickels 7 pennies
0 quarter 1 dime 5 nickels 2 pennies
0 quarter 2 dimes 0 nickels 17 pennies
0 quarter 2 dimes 1 nickel 12 pennies
0 quarter 2 dimes 2 nickels 7 pennies
0 quarter 2 dimes 3 nickels 2 pennies
0 quarter 3 dimes 0 nickels 7 pennies
0 quarter 3 dimes 1 nickel 2 pennies
1 quarter 0 dimes 0 nickels 12 pennies
1 quarter 0 dimes 1 nickel 7 pennies
1 quarter 0 dimes 2 nickels 2 pennies
1 quarter 1 dime 0 nickels 2 pennies
Дэниел С. Собрал
источник
1

Эта моя запись в блоге решает эту проблему, как рюкзак, для фигур из комикса XKCD . Простое изменение слова itemsи exactcostзначения также даст все решения вашей проблемы.

Если проблема заключалась в том, чтобы найти изменение, которое потребовало наименьшей стоимости, то наивный жадный алгоритм, который использовал бы как можно больше монет самой высокой стоимости, вполне мог бы потерпеть неудачу для некоторых комбинаций монет и целевой суммы. Например, если есть монеты достоинством 1, 3 и 4; а целевая сумма равна 6, тогда жадный алгоритм может предложить три монеты номиналом 4, 1 и 1, когда легко увидеть, что вы можете использовать две монеты номиналом 3 каждая.

  • Пэдди.
Paddy3118
источник
1
public class Coins {

static int ac = 421;
static int bc = 311;
static int cc = 11;

static int target = 4000;

public static void main(String[] args) {


    method2();
}

  public static void method2(){
    //running time n^2

    int da = target/ac;
    int db = target/bc;     

    for(int i=0;i<=da;i++){         
        for(int j=0;j<=db;j++){             
            int rem = target-(i*ac+j*bc);               
            if(rem < 0){                    
                break;                  
            }else{                  
                if(rem%cc==0){                  
                    System.out.format("\n%d, %d, %d ---- %d + %d + %d = %d \n", i, j, rem/cc, i*ac, j*bc, (rem/cc)*cc, target);                     
                }                   
            }                   
        }           
    }       
}
 }
Амит Патил
источник
1

Я нашел этот аккуратный фрагмент кода в книге Орейли «Python для анализа данных». Он использует ленивую реализацию и сравнение int, и я предполагаю, что его можно изменить для других номиналов с помощью десятичных знаков. Сообщите мне, как это работает для вас!

def make_change(amount, coins=[1, 5, 10, 25], hand=None):
 hand = [] if hand is None else hand
 if amount == 0:
 yield hand
 for coin in coins:
 # ensures we don't give too much change, and combinations are unique
 if coin > amount or (len(hand) > 0 and hand[-1] < coin):
 continue
 for result in make_change(amount - coin, coins=coins,
 hand=hand + [coin]):
 yield result

Suhas
источник
1

Это улучшение ответа Зихана. Множество ненужных петель возникает, когда номинал составляет всего 1 цент.

Это интуитивно понятно и нерекурсивно.

    public static int Ways2PayNCents(int n)
    {
        int numberOfWays=0;
        int cent, nickel, dime, quarter;
        for (quarter = 0; quarter <= n/25; quarter++)
        {
            for (dime = 0; dime <= n/10; dime++)
            {
                for (nickel = 0; nickel <= n/5; nickel++)
                {
                    cent = n - (quarter * 25 + dime * 10 + nickel * 5);
                    if (cent >= 0)
                    {
                        numberOfWays += 1;
                        Console.WriteLine("{0},{1},{2},{3}", quarter, dime, nickel, cent);
                    }                   
                }
            }
        }
        return numberOfWays;            
    }
Aerin
источник
Вы не можете обобщить это решение, поэтому, например, появляется новый элемент, в этом случае вам нужно добавить еще один цикл for
Sumit Kumar Saha
1

Простое решение Java:

public static void main(String[] args) 
{    
    int[] denoms = {4,2,3,1};
    int[] vals = new int[denoms.length];
    int target = 6;
    printCombinations(0, denoms, target, vals);
}


public static void printCombinations(int index, int[] denom,int target, int[] vals)
{
  if(target==0)
  {
    System.out.println(Arrays.toString(vals));
    return;
  }
  if(index == denom.length) return;   
  int currDenom = denom[index];
  for(int i = 0; i*currDenom <= target;i++)
  {
    vals[index] = i;
    printCombinations(index+1, denom, target - i*currDenom, vals);
    vals[index] = 0;
  }
}
GR44
источник
1
/*
* make a list of all distinct sets of coins of from the set of coins to
* sum up to the given target amount.
* Here the input set of coins is assumed yo be {1, 2, 4}, this set MUST
* have the coins sorted in ascending order.
* Outline of the algorithm:
* 
* Keep track of what the current coin is, say ccn; current number of coins
* in the partial solution, say k; current sum, say sum, obtained by adding
* ccn; sum sofar, say accsum:
*  1) Use ccn as long as it can be added without exceeding the target
*     a) if current sum equals target, add cc to solution coin set, increase
*     coin coin in the solution by 1, and print it and return
*     b) if current sum exceeds target, ccn can't be in the solution, so
*        return
*     c) if neither of the above, add current coin to partial solution,
*        increase k by 1 (number of coins in partial solution), and recuse
*  2) When current denomination can no longer be used, start using the
*     next higher denomination coins, just like in (1)
*  3) When all denominations have been used, we are done
*/

#include <iostream>
#include <cstdlib>

using namespace std;

// int num_calls = 0;
// int num_ways = 0;

void print(const int coins[], int n);

void combine_coins(
                   const int denoms[], // coins sorted in ascending order
                   int n,              // number of denominations
                   int target,         // target sum
                   int accsum,         // accumulated sum
                   int coins[],        // solution set, MUST equal
                                       // target / lowest denom coin
                   int k               // number of coins in coins[]
                  )
{

    int  ccn;   // current coin
    int  sum;   // current sum

    // ++num_calls;

    for (int i = 0; i < n; ++i) {
        /*
         * skip coins of lesser denomination: This is to be efficient
         * and also avoid generating duplicate sequences. What we need
         * is combinations and without this check we will generate
         * permutations.
         */
        if (k > 0 && denoms[i] < coins[k - 1])
            continue;   // skip coins of lesser denomination

        ccn = denoms[i];

        if ((sum = accsum + ccn) > target)
            return;     // no point trying higher denominations now


        if (sum == target) {
            // found yet another solution
            coins[k] = ccn;
            print(coins, k + 1);
            // ++num_ways;
            return;
        }

        coins[k] = ccn;
        combine_coins(denoms, n, target, sum, coins, k + 1);
    }
}

void print(const int coins[], int n)
{
    int s = 0;
    for (int i = 0; i < n; ++i) {
        cout << coins[i] << " ";
        s += coins[i];
    }
    cout << "\t = \t" << s << "\n";

}

int main(int argc, const char *argv[])
{

    int denoms[] = {1, 2, 4};
    int dsize = sizeof(denoms) / sizeof(denoms[0]);
    int target;

    if (argv[1])
        target = atoi(argv[1]);
    else
        target = 8;

    int *coins = new int[target];


    combine_coins(denoms, dsize, target, 0, coins, 0);

    // cout << "num calls = " << num_calls << ", num ways = " << num_ways << "\n";

    return 0;
}
RPK
источник
1

Вот функция C #:

    public static void change(int money, List<int> coins, List<int> combination)
    {
        if(money < 0 || coins.Count == 0) return;
        if (money == 0)
        {
            Console.WriteLine((String.Join("; ", combination)));
            return;
        }

        List<int> copy = new List<int>(coins);
        copy.RemoveAt(0);
        change(money, copy, combination);

        combination = new List<int>(combination) { coins[0] };
        change(money - coins[0], coins, new List<int>(combination));
    }

Используйте это так:

change(100, new List<int>() {5, 10, 25}, new List<int>());

Он печатает:

25; 25; 25; 25
10; 10; 10; 10; 10; 25; 25
10; 10; 10; 10; 10; 10; 10; 10; 10; 10
5; 10; 10; 25; 25; 25
5; 10; 10; 10; 10; 10; 10; 10; 25
5; 5; 10; 10; 10; 10; 25; 25
5; 5; 10; 10; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 10; 25; 25; 25
5; 5; 5; 10; 10; 10; 10; 10; 10; 25
5; 5; 5; 5; 10; 10; 10; 25; 25
5; 5; 5; 5; 10; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 25; 25; 25
5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 10; 10; 25; 25
5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 10; 25; 25
5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 25; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 25
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 10
5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5; 5
Shinzou
источник
Результат
Спасибо
1

Ниже представлена ​​программа на Python, которая позволяет найти все комбинации денег. Это решение динамического программирования с порядком (n) времени. Деньги 1,5,10,25

Переходим от денег 1-го ряда к деньгам 25 (4 ряда). Строка денег 1 содержит счет, если мы учитываем только деньги 1 при подсчете количества комбинаций. Строка money 5 создает каждый столбец, беря счет в строке money r для тех же конечных денег плюс предыдущие 5 счетчиков в собственной строке (текущая позиция минус 5). Строка денег 10 использует строку денег 5, которая содержит счет как для 1,5, так и для суммирования в предыдущих 10 счетах (текущая позиция минус 10). Деньги строки 25 используют деньги строки 10, которые содержат счетчики для денег строки 1,5,10 плюс предыдущие 25.

Например, числа [1] [12] = числа [0] [12] + числа [1] [7] (7 = 12-5) », что дает 3 = 1 + 2; числа [3] [12] = числа [2] [12] + числа [3] [9] (-13 = 12-25), что приводит к 4 = 0 + 4, так как -13 меньше 0.

def cntMoney(num):
    mSz = len(money)
    numbers = [[0]*(1+num) for _ in range(mSz)]
    for mI in range(mSz): numbers[mI][0] = 1
    for mI,m in enumerate(money):
        for i in range(1,num+1):
            numbers[mI][i] = numbers[mI][i-m] if i >= m else 0
            if mI != 0: numbers[mI][i] += numbers[mI-1][i]
        print('m,numbers',m,numbers[mI])
    return numbers[mSz-1][num]

money = [1,5,10,25]
    num = 12
    print('money,combinations',num,cntMoney(num))

output:    
('m,numbers', 1, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
('m,numbers', 5, [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3])
('m,numbers', 10, [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4])
('m,numbers', 25, [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4])
('money,combinations', 12, 4)
EdW
источник
0

Решение Java

import java.util.Arrays;
import java.util.Scanner;


public class nCents {



public static void main(String[] args) {

    Scanner input=new Scanner(System.in);
    int cents=input.nextInt();
    int num_ways [][] =new int [5][cents+1];

    //putting in zeroes to offset
    int getCents[]={0 , 0 , 5 , 10 , 25};
    Arrays.fill(num_ways[0], 0);
    Arrays.fill(num_ways[1], 1);

    int current_cent=0;
    for(int i=2;i<num_ways.length;i++){

        current_cent=getCents[i];

        for(int j=1;j<num_ways[0].length;j++){
            if(j-current_cent>=0){
                if(j-current_cent==0){
                    num_ways[i][j]=num_ways[i-1][j]+1;
                }else{
                    num_ways[i][j]=num_ways[i][j-current_cent]+num_ways[i-1][j];
                }
            }else{
                num_ways[i][j]=num_ways[i-1][j];
            }


        }


    }



    System.out.println(num_ways[num_ways.length-1][num_ways[0].length-1]);

}

}

Медведь
источник
0

Нижеприведенное java-решение, которое также распечатает различные комбинации. Легко понять. Идея

на сумму 5

Решение

    5 - 5(i) times 1 = 0
        if(sum = 0)
           print i times 1
    5 - 4(i) times 1 = 1
    5 - 3 times 1 = 2
        2 -  1(j) times 2 = 0
           if(sum = 0)
              print i times 1 and j times 2
    and so on......

Если оставшаяся сумма в каждом цикле меньше номинала, т.е. если оставшаяся сумма 1 меньше 2, то просто прервите цикл.

Полный код ниже

Пожалуйста, поправьте меня в случае ошибок

public class CoinCombinbationSimple {
public static void main(String[] args) {
    int sum = 100000;
    printCombination(sum);
}

static void printCombination(int sum) {
    for (int i = sum; i >= 0; i--) {
        int sumCopy1 = sum - i * 1;
        if (sumCopy1 == 0) {
            System.out.println(i + " 1 coins");
        }
        for (int j = sumCopy1 / 2; j >= 0; j--) {
            int sumCopy2 = sumCopy1;
            if (sumCopy2 < 2) {
                break;
            }
            sumCopy2 = sumCopy1 - 2 * j;
            if (sumCopy2 == 0) {
                System.out.println(i + " 1 coins " + j + " 2 coins ");
            }
            for (int k = sumCopy2 / 5; k >= 0; k--) {
                int sumCopy3 = sumCopy2;
                if (sumCopy2 < 5) {
                    break;
                }
                sumCopy3 = sumCopy2 - 5 * k;
                if (sumCopy3 == 0) {
                    System.out.println(i + " 1 coins " + j + " 2 coins "
                            + k + " 5 coins");
                }
            }
        }
    }
}

}

FatherMathew
источник
0

Вот решение на основе Python, которое использует рекурсию, а также мемоизацию, что приводит к сложности O (mxn)

    def get_combinations_dynamic(self, amount, coins, memo):
    end_index = len(coins) - 1
    memo_key = str(amount)+'->'+str(coins)
    if memo_key in memo:
        return memo[memo_key]
    remaining_amount = amount
    if amount < 0:
        return []
    if amount == 0:
        return [[]]
    combinations = []
    if len(coins) <= 1:
        if amount % coins[0] == 0:
            combination = []
            for i in range(amount // coins[0]):
                combination.append(coins[0])
            list.sort(combination)
            if combination not in combinations:
                combinations.append(combination)
    else:
        k = 0
        while remaining_amount >= 0:
            sub_combinations = self.get_combinations_dynamic(remaining_amount, coins[:end_index], memo)
            for combination in sub_combinations:
                temp = combination[:]
                for i in range(k):
                    temp.append(coins[end_index])
                list.sort(temp)
                if temp not in combinations:
                    combinations.append(temp)
            k += 1
            remaining_amount -= coins[end_index]
    memo[memo_key] = combinations
    return combinations
оборота лалатнаяк
источник
Хорошо, я сомневаюсь, что у приведенного выше есть полиномиальное время выполнения. Не уверен, что у нас вообще может быть полиномиальное время выполнения. Но я заметил, что во многих случаях вышеупомянутая версия работает быстрее, чем незарегистрированная версия. Я продолжу исследовать, почему
lalatnayak