So finden Sie alle Münzkombinationen, wenn Sie einen bestimmten Dollarwert erhalten
Ich habe vor ein paar Monaten einen Code gefunden, den ich für die Vorbereitung auf ein Vorstellungsgespräch geschrieben habe.
Nach dem Kommentar, den ich hatte, versuchte es, dieses Problem zu lösen:
Suchen Sie bei einem bestimmten Dollarwert in Cent (z. B. 200 = 2 Dollar, 1000 = 10 Dollar) alle Kombinationen von Münzen, die den Dollarwert ausmachen. Es sind nur Pennys (1 ¢), Nickel (5 ¢), Groschen (10 ¢) und Viertel (25 ¢) zulässig.
Wenn beispielsweise 100 angegeben wurde, sollte die Antwort lauten:
4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies
3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies
etc.
Ich glaube, dass dies sowohl iterativ als auch rekursiv gelöst werden kann. Meine rekursive Lösung ist ziemlich fehlerhaft, und ich habe mich gefragt, wie andere Leute dieses Problem lösen würden. Der schwierige Teil dieses Problems bestand darin, es so effizient wie möglich zu gestalten.
Ich habe es mir vor langer Zeit einmal angesehen, und Sie können meine kleine Beschreibung darüber lesen . Hier ist die Mathematica-Quelle .
Durch die Verwendung von Generierungsfunktionen erhalten Sie eine zeitlich geschlossene Lösung für das Problem. Graham, Knuth und Patashniks Konkrete Mathematik ist das Buch dafür und enthält eine ziemlich ausführliche Diskussion des Problems. Im Wesentlichen definieren Sie ein Polynom, bei dem der Koeffizient n die Anzahl der Änderungsmöglichkeiten für n Dollar ist.
Die Seiten 4-5 der Beschreibung zeigen, wie Sie Mathematica (oder ein anderes geeignetes Computeralgebrasystem) verwenden können, um die Antwort für 10 ^ 10 ^ 6 Dollar in wenigen Sekunden in drei Codezeilen zu berechnen.
(Und das ist lange genug her, dass das auf einem 75-MHz-Pentium ein paar Sekunden sind ...)
Hinweis: Dies zeigt nur die Anzahl der Wege.
Scala-Funktion:
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)
Ich würde eine rekursive Lösung bevorzugen. Sie haben eine Liste mit Stückelungen. Wenn die kleinste Liste einen verbleibenden Währungsbetrag gleichmäßig aufteilt, sollte dies problemlos funktionieren.
Grundsätzlich wechseln Sie vom größten zum kleinsten Nennwert.
Rekursiv,
- Sie haben eine aktuelle Summe zu füllen und eine größte Stückelung (mit mehr als 1 übrig). Wenn nur noch 1 Stückelung übrig ist, gibt es nur noch eine Möglichkeit, die Gesamtsumme zu füllen. Sie können 0 bis k Kopien Ihres aktuellen Nennwerts verwenden, sodass k * cur denomination <= total ist.
- Rufen Sie für 0 bis k die Funktion mit der geänderten Summe und dem neuen größten Nennwert auf.
- Addiere die Ergebnisse von 0 zu k. Auf diese Weise können Sie Ihre Gesamtsumme ab dem aktuellen Nennwert abwärts füllen. Geben Sie diese Nummer zurück.
Hier ist meine python Version Ihres angegebenen Problems für 200 Cent. Ich erhalte 1463 Möglichkeiten. Diese Version druckt alle Kombinationen und die endgültige Gesamtanzahl.
#!/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)
Scala-Funktion:
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
}
Hier ist ein absolut unkomplizierter C++ - Code zur Lösung des Problems, bei dem alle Kombinationen angezeigt werden mussten.
#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;
}
Aber ich bin ziemlich fasziniert von dem Unterproblem, nur die Anzahl der Kombinationen zu berechnen. Ich vermute, es gibt eine geschlossene Gleichung dafür.
Dies ist eine sehr alte Frage, aber ich habe eine rekursive Lösung in Java) gefunden, die kleiner zu sein schien als alle anderen.
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);
}
}
Verbesserungen:
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);
}
}
Der Code verwendet Java, um dieses Problem zu lösen, und es funktioniert auch ... Diese Methode ist möglicherweise keine gute Idee, da zu viele Schleifen vorhanden sind, aber es ist wirklich ein einfacher Weg.
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));
}
}
Das Unterproblem ist ein typisches Problem der dynamischen Programmierung.
/* 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;
}
Sei C (i, J) die Menge von Kombinationen, um i Cent unter Verwendung der Werte in der Menge J zu machen.
Sie können C folgendermaßen definieren:
(first (J) nimmt deterministisch ein Element einer Menge)
Es stellt sich heraus, dass es eine ziemlich rekursive Funktion ist ... und einigermaßen effizient, wenn Sie Memoization verwenden;)
semi-Hack, um das einzigartige Kombinationsproblem zu umgehen - absteigende Reihenfolge erzwingen:
$ 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
Dies wird langsam ablaufen, da es nicht auswendig gelernt wird, aber Sie bekommen die Idee.
# 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;
}
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);
}
Dies ist meine Antwort in Python. Es wird keine Rekursion verwendet:
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 __== "__main__":
coins = [25,10,5,1]
target = 78
print breakit(target, coins)
Beispielausgabe
...
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
Beides: Durchlaufen Sie alle Nennwerte von hoch nach niedrig, nehmen Sie einen von Nennwerten, subtrahieren Sie von der erforderlichen Gesamtsumme und wiederholen Sie den Rest (Beschränken Sie die verfügbaren Nennwerte auf den aktuellen Iterationswert oder einen niedrigeren Wert).
Ich weiß, das ist eine sehr alte Frage. Ich suchte nach der richtigen Antwort und konnte nichts finden, was einfach und zufriedenstellend ist. Hat einige Zeit gedauert, konnte aber etwas aufschreiben.
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 );
Dies ist eine Javascript-Lösung und verwendet Rekursion.
Wenn das Währungssystem dies zulässt, wird mit einem einfachen gierigen Algorithmus von jeder Münze so viel wie möglich genommen, beginnend mit der Währung mit dem höchsten Wert.
Andernfalls ist eine dynamische Programmierung erforderlich, um schnell eine optimale Lösung zu finden, da dieses Problem im Wesentlichen das Rucksackproblem ist.
Zum Beispiel, wenn ein Währungssystem die Münzen hat: {13, 8, 1}, die gierige Lösung würde sich für 24 ändern, da {13, 8, 1, 1, 1}, aber die wirklich optimale Lösung ist {8, 8, 8}
Bearbeiten: Ich dachte, wir würden Änderungen optimal durchführen und nicht alle Möglichkeiten auflisten, wie Sie Änderungen für einen Dollar vornehmen können. In meinem letzten Interview habe ich gefragt, wie ich Änderungen vornehmen soll, und bin dann weitergegangen, bevor ich die Frage gelesen habe.
In Scala Programmiersprache würde ich es so machen:
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)
}
}
Ich habe dieses nette Stück Code in dem Buch "Python For Data Analysis" von O'reily gefunden. Es verwendet Lazy Implementierung und Int Vergleich und ich nehme an, dass es für andere Bezeichnungen mit Dezimalstellen geändert werden kann. Lassen Sie mich wissen, wie es bei Ihnen funktioniert!
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 resultHier ist eine C # -Funktion:
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));
}
Benutze es so:
change(100, new List<int>() {5, 10, 25}, new List<int>());
Es druckt:
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
Hierbei handelt es sich um einen einfachen rekursiven Algorithmus, bei dem eine Rechnung rekursiv und eine kleinere Rechnung rekursiv verarbeitet wird, bis die Summe erreicht ist. Anschließend wird eine weitere Rechnung mit demselben Nennwert verarbeitet und erneut verarbeitet. Siehe Beispielausgabe unten zur Veranschaulichung.
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, "");
Druckt Folgendes aus:
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
Duh, ich fühle mich gerade dumm. Unten gibt es eine zu komplizierte Lösung, die ich beibehalten werde, weil es ist schließlich eine Lösung ist. Eine einfache Lösung wäre:
// 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"
Hier ist die andere Lösung. Diese Lösung basiert auf der Beobachtung, dass jede Münze ein Vielfaches der anderen ist, so dass sie in Bezug auf sie dargestellt werden können.
// 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"
}
Für 37 Münzen zum Beispiel:
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
Dies ist die Verbesserung von Zihans Antwort. Die meisten unnötigen Schleifen entstehen, wenn der Nennwert nur 1 Cent beträgt.
Es ist intuitiv und nicht rekursiv.
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;
}
/*
* 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;
}
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);
}
}
}
}
}
}
Dieser Blogeintrag von mir löst dieses rucksackartige Problem für die Figuren aus einem XKCD-Comic . Eine einfache Änderung des items -Dikts und des exactcost -Wertes ergibt auch für Ihr Problem alle Lösungen.
Wenn das Problem darin besteht, die Änderung zu finden, die die geringsten Kosten verursacht hat, kann ein naiver, gieriger Algorithmus, der so viel von der Münze mit dem höchsten Wert verwendet, für einige Kombinationen von Münzen und Zielbetrag fehlschlagen. Zum Beispiel, wenn es Münzen mit den Werten 1, 3 und 4 gibt; und der Zielbetrag ist 6, dann schlägt der Greedy-Algorithmus möglicherweise drei Münzen mit den Werten 4, 1 und 1 vor, wenn leicht zu erkennen ist, dass Sie jeweils zwei Münzen mit dem Wert 3 verwenden können.
- Paddy.
Einfache Java Lösung:
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;
}
}
Hier ist eine python basierte Lösung, die sowohl Rekursion als auch Memoisierung verwendet, was zu einer Komplexität von O (mxn) führt.
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
Viele Variationen hier, aber ich konnte keine PHP) - Lösung für die Anzahl der Kombinationen finden, also werde ich eine hinzufügen.
/**
* @param int $money The total value
* @param array $coins The coin denominations
* @param int $sum The countable sum
* @return int
*/
function getTotalCombinations($money, $coins, &$sum = 0){
if ($money == 0){
return $sum++;
} else if (empty($coins) || $money < 0){
return $sum;
} else {
$firstCoin = array_pop(array_reverse($coins));
getTotalCombinations($money - $firstCoin, $coins, $sum) + getTotalCombinations($money, array_diff($coins, [$firstCoin]), $sum);
}
return $sum;
}
$totalCombinations = getTotalCombinations($money, $coins);
PHP Code um einen Betrag in Stückelungen aufzuteilen:
//Define the denominations
private $denominations = array(1000, 500, 200, 100, 50, 40, 20, 10, 5, 1);
/**
* S# countDenomination() function
*
* @author Edwin Mugendi <[email protected]>
*
* Count denomination
*
* @param float $original_amount Original amount
*
* @return array with denomination and count
*/
public function countDenomination($original_amount) {
$amount = $original_amount;
$denomination_count_array = array();
foreach ($this->denominations as $single_denomination) {
$count = floor($amount / $single_denomination);
$denomination_count_array[$single_denomination] = $count;
$amount = fmod($amount, $single_denomination);
}//E# foreach statement
var_dump($denomination_count_array);
return $denomination_count_array;
//return $denomination_count_array;
}
// E # countDenomination () Funktion
Die folgende Java Lösung, die auch die verschiedenen Kombinationen druckt. Einfach zu verstehen. Idee ist
für die Summe 5
Die Lösung ist
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......
Wenn die verbleibende Summe in jeder Schleife kleiner als der Nennwert ist, dh wenn die verbleibende Summe 1 kleiner als 2 ist, unterbrechen Sie einfach die Schleife
Der vollständige Code unten
Bitte korrigieren Sie mich bei Fehlern
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");
}
}
}
}
}
}
Unten ist python Lösung:
x = []
dic = {}
def f(n,r):
[a,b,c,d] = r
if not dic.has_key((n,a,b,c,d)): dic[(n,a,b,c,d)] = 1
if n>=25:
if not dic.has_key((n-25,a+1,b,c,d)):f(n-25,[a+1,b,c,d])
if not dic.has_key((n-10,a,b+1,c,d)):f(n-10,[a,b+1,c,d])
if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
Elif n>=10:
if not dic.has_key((n-10,a,b+1,c,d)):f(n-10,[a,b+1,c,d])
if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
Elif n>=5:
if not dic.has_key((n-5,a,b,c+1,d)):f(n-5,[a,b,c+1,d])
if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
Elif n>=1:
if not dic.has_key((n-1,a,b,c,d+1)):f(n-1,[a,b,c,d+1])
else:
if r not in x:
x.extend([r])
f(100, [0,0,0,0])
print x
Java-Lösung
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]);
}
}