Hallo Leute,
Ich hab folgende Aufgabe bekommen:

Eingabe sind verschiedene Münzen mit je einer Wertigkeit und Anzahl der jeweiligen Münzen.
Diese soll ich auf n Töchter verteilen.
Ich soll also überprüfen ob ich mit den gegebenen Münzen alle zum gleichen Wert auf die n töchter genau aufteilen kann. (rekursiv)

Meine Idee:
Die werte der münzen(key) und ihre anzahl (value) in ein treemap zu speichern und mit dieser zu rechnen

dann erstmal überprüfen ob der gesammtbetrag durch die n töchter zu teilen sind

wenn ja

gesamt durch n rechnen um anteile der einzelnen töchter zu beckommen

nehme ich die map und versuche vom größten münzwert angefangen den ersten teil der ersten tochter zu füllen mit den gegebenen münzen
wenns klappt
weiter zur nächsten
wider auffüllen
weiter zur nächsten
bis zur n ten tochter
wenn ich alle füllen kann klappts wenn nicht(münswerte größer als anteil) brichts ab

FRAGE:
Ist das so OK oder gibt es einene bessere bzw. effizientere Methode dies "rekursiv" zu lösen?

Naja, als rekursive Variante würde mir spontan einfallen eine Methode zu schreiben die mit den Münzen und den Töchtern aufgerufen wird und jeweils eine Münze verteilt und sich dann wieder selber aufruft wenn noch Geld da ist. Ist allerdings eher umständlicher. Ist denn in der Aufgabe explizit angegeben, dass es rekursiv sein muss?


EDIT: Eine weitere Idee wäre, jeder Tochter solange von den größten Münzen zu geben bis von denen keine mehr da sind, die weiteren Töchter die dann noch zu wenig haben aufzufüllen bis zu dem bestimmten Betrag und dann mit der nächst größeren Münze weiter zu machen

Danke für deine Idee, ich bin aber nicht sicher ob es zeitlicher Effizienter wäre.

Das Programm muss rekursiv geschrieben und möglichst Zeiteffizient sein.

rekursiv ist aber nicht effizient.

Ich finde die Aufgabe klingt nach einen typischen Fall für Backtracking...

Da gebe ich dir ja recht genodeftest, aber so lautet nun mal leider die Aufgabe. Der Tipp mit dem Backtrapping ist gut. Darüber haben wir auch vor einiger Zeit mal gesprochen.

Ich musste heute mein UML dazu abgeben und nach ein paar kleinen Fehlerkorrekturen wurde es abgenommen. Die umsetzung wird sicherlich etwas komplizierter, aber noch machbar für mich.

Danke für eure Hilfe