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

4 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.

Kommentar verfassen