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

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

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

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

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

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

• Пэдди.

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

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

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

Вот моя версия заявленной вами проблемы для 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)

Вот какой-то абсолютно простой код на 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;
}

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

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

Вы можете определить C следующим образом:

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

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

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

// 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

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

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

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

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

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

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

$denoms = [1,5,10,25]
def all_combs(sum,last) 
  return 1 if sum == 0
  return $denoms.select{|d| d &le sum && d &le last}.inject(0) {|total,denom|
           total+all_combs(sum-denom,denom)}
end

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