Anzahl Möglichkeiten feste Summe aus Münzen zu berechnen

Question

In dieser Aufgabe soll die Anzahl Möglichkeiten berechnet werden, aus 1;2;5;10;20;50;100 und200 Cent-Münzen eine festgelegte Summe exakt zu erhalten.
Man muss das ganze in Java implementieren. Die Münzen sind als Liste zur Verfügung gestellt.Folgende Methode soll man vervollständigen:

static int numPossibilities(int sum, int max, List<Integer> remainingCoins){

}

Meine Idee ist es die Aufgabe mit der Partitionsfunktion zu lösen,allerdings weiß ich nicht,wie ich n und k umsetzen soll und die Münzen miteinbringe.

Partitionsfunktion:

https://de.wikipedia.org/wiki/Partitionsfunktion

Danke für eure hilfe

Comments

Auch TU-München? :D
Hast du schon eine Antwort?

Answer 1

Wie ist das mit einem rekursiven Ansatz.

Also du gehst die Liste an Münzen durch. Sobald du eine Münze wegnehmen kannst erhöhst du die Möglichkeiten um 1 und dann noch um die Anzahl der Möglichkeiten wenn du diese Münze weggenommen hast.

Sobald du noch eine Münze wegnehmen kannst erhöhst du die Möglichkeiten um 1 und dann noch um die Anzahl der Möglichkeiten wenn du auch diese Münze weggenommen hast.
In der nächsten Rekursionsstufe stehen dir dann nur noch Münzen einer niedrigeren Wertigkeit zur Verfügung.

Comments

ich hab das leider nicht ganz verstanden,
wärst du so nett und könntest du das ev anhand eines Beispiels z.B. 5 zeigen?
würde mir sehr weiterhelfen
vielen Dank