031 – Möglichkeiten, 2 Euro aus verschiedenen Münzen zu kombinieren

 

Es sind acht unterschiedliche Euromünzen im Umlauf:

1ct, 2ct, 5ct, 10ct, 20ct, 50ct, 1€ (100ct) und 2€ (200ct).

Zwei Euro (200ct) können zum Beispiel wie folgt kombiniert werden:

1\cdot 100ct + 1\cdot 50ct + 2\cdot 20ct + 1\cdot 5ct + 1\cdot 2ct + 3\cdot 1ct = 200ct

Wie viele unterschiedliche Möglichkeiten (ohne Beachtung der Reihenfolge der Münzen) gibt es?

Lösung

Diese Aufgabe ist schwieriger als die vorherigen. Es gibt eine Vielzahl an möglichen Lösungsalgorithmen (rekursiv oder mit dynamic programming). Hier soll nur einer erklärt werden.

Wir überlegen zunächst, wie viele Möglichkeiten es gibt, eine Summe nur aus 1ct Münzen zu kombinieren:

\begin{array}{*{20}{c}}    {Summe} &\vline &  0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & {10} & {11} & {12} & {13} & {14} & {15} & {16} & {17}  \\ \hline    {1ct} &\vline &  1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1  \\   \end{array}

Es gibt immer genau eine Möglichkeit, nämlich die, den gewünschten Betrag aus der entsprechenden Anzahl an 1ct Münzen zu addieren. Nun nehmen wir die 2ct Münzen hinzu. Bei 0ct und 1ct hilft uns diese Münze nicht, sie wird erst bei 2ct interessant. Dort verschafft sie uns neben der Möglichkeit, die 2ct aus zwei 1ct Münzen zu kombinieren, die Alternative, nur die 2ct Münze zu benutzen. Das gleiche gilt für 3ct:

\begin{array}{*{20}{c}}    {Summe} &\vline &  0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & {10} & {11} & {12} & {13} & {14} & {15} & {16} & {17}  \\ \hline    {1ct} &\vline &  1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1  \\    {2ct} &\vline &  1 & 1 & 2 & 2 & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {} & {}  \\   \end{array}

Bei 4ct haben wir nun drei Möglichkeiten, bei 6ct schon 4 und so weiter. Wir können die Anzahl der Möglichkeiten berechnen, indem wir bei 2ct anfangen und jeweils die Anzahl der Möglichkeiten zwei weiter links zu der Anzahl der Möglichkeiten nur mit 1ct addieren:

2ct: 1 + 1 = 2
3ct: 1 + 1 = 2
4ct: 1 + 2 = 3
5ct: 1 + 2 = 3

17ct: 1 + 8 = 9

\begin{array}{*{20}{c}}    {Summe} &\vline &  0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & {10} & {11} & {12} & {13} & {14} & {15} & {16} & {17}  \\ \hline    {1ct} &\vline &  1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1  \\    { + 2ct} &\vline &  1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5 & 6 & 6 & 7 & 7 & 8 & 8 & 9 & 9  \\   \end{array}

Wir verfahren genau so mit den 5ct Münzen. Die ersten Summen von 0 bis 4 Cent übernehmen wir aus der Zeile für 2ct Kombinationen, da wir diese mit einer 5 Cent Münze nicht beeinflussen können.

\begin{array}{*{20}{c}} {Summe}&\vline&0&1&2&3&4&5&6&7&8&9&{10}&{11}&{12}&{13}&{14}&{15}&{16}&{17}\\ \hline {1ct}&\vline&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\ { + 2ct}&\vline&1&1&2&2&3&3&4&4&5&5&6&6&7&7&8&8&9&9\\ { + 5ct}&\vline&1&1&2&2&3&{}&{}&{}&{}&{}&{}&{}&{}&{}&{}&{}&{}&{} \end{array}

Ab der Summe für 5 Cent übernehmen wir ebenfalls die Anzahl aus der Zeile für 2ct, addieren aber die Anzahl aus der Zeile für 5ct jeweils 5 Positionen weiter links. Bei 5 Cent wird also 1 addiert, bei 6 Cent auch 1, bei 7 Cent 2, und so weiter.

\begin{array}{*{20}{c}} {Summe}&\vline&0&1&2&3&4&5&6&7&8&9&{10}&{11}&{12}&{13}&{14}&{15}&{16}&{17}\\ \hline {1ct}&\vline&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\ { + 2ct}&\vline&1&1&2&2&3&3&4&4&5&5&6&6&7&7&8&8&9&9\\ { + 5ct}&\vline&1&1&2&2&3&4&5&6&7&8&{10}&{11}&{13}&{14}&{16}&{18}&{20}&{22} \end{array}

Bei 10 Cent verfahren wir genauso, lassen aber die ersten 10 Summen wie bei 5 Cent und addieren ab der Summe für 10 Cent jeweils die Summe 10 Stellen weiter links:

\begin{array}{*{20}{c}} {Summe}&\vline&0&1&2&3&4&5&6&7&8&9&{10}&{11}&{12}&{13}&{14}&{15}&{16}&{17}\\ \hline {1ct}&\vline&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\ { + 2ct}&\vline&1&1&2&2&3&3&4&4&5&5&6&6&7&7&8&8&9&9\\ { + 5ct}&\vline&1&1&2&2&3&4&5&6&7&8&{10}&{11}&{13}&{14}&{16}&{18}&{20}&{22}\\ { + 10ct}&\vline&1&1&2&2&3&4&5&6&7&8&{11}&{12}&{15}&{16}&{19}&{22}&{25}&{28} \end{array}

Dies lassen wir bis 200ct und mit allen Münzen durchlaufen. Da Matlab Arrays mit 1 statt mit 0 anfangen, müssen wir den Index um 1 verschieben.

Matlab-Code:

function moglich = e031(ziel)
    tic
    munzen = [1 2 5 10 20 50 100 200];
    verschiedeneMunzen = length(munzen);
    mogl = zeros(1, ziel+1);
    mogl(1) = 1;

    for m = 1 : verschiedeneMunzen
        for j = munzen(m) + 1 : ziel +1
            mogl(j) = mogl(j) + mogl(j - munzen(m));
        end
    end
    moglich = mogl(ziel+1);
    toc;
end

Ergebnis: 73682
Rechenzeit: 0.000045 Sekunden

Ähnliche Artikel

5 Kommentare zu “031 – Möglichkeiten, 2 Euro aus verschiedenen Münzen zu kombinieren”

Die Lösung ist nicht ganz korrekt.
Bei meiner Lösung ist die Anzahl der Möglichkeiten z.B. bei 10 zu wenig.
ist man bei der Summe 10 und bezieht die anzahl der Möglichkeiten bis zur 10 Cent Münze in betracht, so fehlt hier eine Möglichkeit.

1. 1+1+1+1+1+1+1+1+1+1
2. 1+1+1+1+1+1+1+1+2
3. 1+1+1+1+1+1+2+2
4. 1+1+1+1+2+2+2
5. 1+1+2+2+2+2
6. 2+2+2+2+2
7. 5+1+1+1+1+1
8. 5+1+1+1+2
9. 5+1+2+2
10. 5+5
11. 10

Meine Lösung ist rekursiv und sieht folgendermaßen (in Java) aus:
/**
* An immutable singly-linked list.
*
* @param
* the type of the list elements
*/
class List {
T head;
List tail;

List(T head, List tail) {
this.head = head;
this.tail = tail;
}

/**
* Generic helper function for list creation. You DO NOT NEED to call this
* function.
*/
static List node(U head, List tail) {
return new List(head, tail);
}
}

public class Muenzen {

/**
* Counts the number of possibilities to get a total value of exactly
* {@code max} using only the values given in {@code remainingCoins}.
*
* @param sum
* the accumulated value
* @param max
* the maximum value
* @param remainingCoins
* a list of coins
* @return the number of possibilities
*/

static int numPossibilities(int sum, int max, List remainingCoins) {
// TODO

int possibilities = 0;

if (max / remainingCoins.head > 0) {
while (sum <= max) {

if (remainingCoins.tail != null) {
possibilities += numPossibilities(sum, max,
remainingCoins.tail);

}
sum = sum + remainingCoins.head;

if (sum == max)
possibilities++;

}

}

return possibilities;
}

public static void main(String[] args) {
// Given a list of coins…
List coins = List
.node(1,
List.node(
2,
List.node(
5,
List.node(10, List.node(20, List.node(
50,
List.node(100,
List.node(200, null))))))));

// For example, the number of possibilities to get a total value of 175
// is 41454.
int result = numPossibilities(0, 10, coins);

System.out.println(“There are ” + result + ” number of ways.”);

}

}

An Studenten der TU München:
Ich rate diese Lösung nicht zu kopieren!
Ansonsten wir es Probleme geben, da dies die von mir eingereichte Lösung ist^^

Ich habe ein Problem die Lösung nachzuvollziehen.

Ich verstehe folgendes nicht,

“Wir können die Anzahl der Möglichkeiten berechnen, indem wir bei 2ct anfangen und jeweils die Anzahl der Möglichkeiten zwei weiter links zu der Anzahl der Möglichkeiten nur mit 1ct addieren.”

bzw. bei 5cent: Wir verfahren genau so mit den 5ct Münzen, nur dass wir nun bei 5ct beginnen und immer die Anzahl der Möglichkeiten 5 Stellen weiter links addieren.

Können sie vielleicht in der Tabelle einmal farbig markieren was sie genau meinen, bzw. auch bei 5 cent noch einmal 3 Rechnungen dazuschreiben. Irgendwie fehlt mir der Blick bzw. ist es mir unklar was gemeint ist.

@Matheton: Danke für den Hinweis. Der Matlab Code war korrekt, ich bin aber beim Erstellen der Tabellen ein Mal in der Spalte verrutscht. Das habe ich korrigiert.

@sebst: Ich habe auch noch eine ausführlichere Erklärung hinzugefügt. Ich hoffe so kann man es besser nachvollziehen.

Moin,

ich weiss der Beitrag ist ca 2,3 Milliarden Jahre alt, aber ich bin drüber gestoßen und hatte anfangs auch etwas Probleme die “x Stellen weiter links” zu interpretieren. Ich bin nicht sicher, ob ich die Lösung vollständig verstanden habe.
Sehe ich das richtig, dass bis zum Wert der Münze alles von der vorhergehenden Münze übernommen wird und sobald der Wert erreicht ist, dann zusätzlich die aktuell ermittelte Anzahl (um Positionen vorher) addiert wird, weil die neue Münze eine neue Möglichkeit bietet den Betrag darzustellen. Alle folgenden Anzahlen des aktuellen Münzwertes addieren dann genau das auf, was vorher schon ermittelt wurde. Wenn ich also bei 5ct Münzwert bin und ein zweites mal die 5ct benutzen kann um den Wert 10 darzustellen, lande ich genau bei dem Wert 5ct wo ich bereits 1 Addiert habe, da ich immer weiter addiere, wird bei jedem mal wo durch 5 erneut teilbar ist, alle vorhergehenden (ich nenne sie jetzt mal Versatzerhöhungen) mitgezogen.

Sehr elegante Lösung!
Kein Vergleich zu meinem Rekursionsgeschleuder. Ich werde mich bei Gelegenheit aber auch mal an eine performate Lösung setzen. Ich bin mir sicher dass da irgendetwas mit modulo zu holen sein wird :)

LG

Kommentar verfassen