[C++] Auf wie viele Weisen kann ich 10 Euro aufteilen?

[DoWe]

Hallo liebe Gemeinde,

folgendes Problem, auf dass ich auch nach längerem Planen auf Blatt Papier nicht zur Lösung komme:

Auf wie viele Möglichkeiten kann ich 10 Euro aufteilen? Hierbei stehen mir alle Münz-und Banknotenarten zur Verfügung.

Die Anforderungen an der Funktion ist folgende:



// PRE: [first , last) is a valid nonempty range that describes
// a sequence of denominations d_1 > d_2 > ... > d_n > 0
// POST: return value is the number of ways to partition amount
// using denominations from d_1 , ... , d_n
unsigned int partitions ( unsigned int amount , const unsigned int* first ,
const unsigned int* last );



Es hapert bei mir an dem Sortieralgorythmus. Ich übergebe der Funktion die Geldmenge, die unterteilt werden soll, sowie die Pointer des Arrays, welches die einzelnen Münz/Notenwerte hält.

Nun weiß ich nicht wie ich weiter vorgehen soll. Eventuell hapert es ja nur an einem kleinen Tipp.


Grüße
DoWe aus CH

[del_4901]

http://de.wikipedia.org/wiki/Rucksackproblem

[Gast]

"Das Rucksackproblem ist ein Optimierungsproblem der Kombinatorik. Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Nutzwert haben..."
Was für zwei Eigenschaften hat Geld denn?

Ich denke mann muss nur alle Kombinationen suchen, mit denen man 10 Euro zusammenstellen kann.
Ich würde wie folgt vorgehen. Die Geldwerte sind ja sortiert. Also fang ich mit dem größten an und mach den Betrag voll. Das ist mein erster Eintrag. Dann nehm ich von dem größten Geldwert einen weniger und mach mit dem nächstkleinerem weiter. so lange, bis der Betrag wieder voll ist. Das ist mein nächster. usw...
Im Beispiel:
amount = 10
coins = [10,5,2,1]

#start
count1 = [0,0,0,0]
#mit der ersten Münze vollmachen:
count1 = [1,0,0,0]
#fertig

#ersten eintrag (>0) runterzählen
count2 = [0,0,0,0]
#mit der zweiten Münze vollmachen
count2 = [0,2,0,0]

#ersten Eintrag (>0) runterzählen
count3 = [0,1,0,0]
#mit der dritten vollmachen
count3 = [0,1,2,0]
#reicht nicht, also mit der 4ten
count3 = [0,1,2,1]

#ersten Eintrag (>0) runterzählen
count3 = [0,0,0,0]
#mit der dritten vollmachen
count3 = [0,0,5,0]

usw...
Die schnell zusammengeschusterte Python version findet überraschende 888 verschiedene Kombinationen. (bei coins = [10,5,2,1,.5,.2,.1,.05,.02,.01])
Das einzig spannende ist es, zu merken welche alte Aufteilung man als Vorlage für den nächsten Schritt nimmt.

[Trap]

Nein, das ist kein Rucksackproblem (es fehlt die Größe nach der optimiert werden soll).

Es ist auch allgemein kein Optimierungsproblem, es geht nur darum die Zahl der möglichen Lösungen zu finden. Wahrscheinlich kann man das auch direkt ausrechnen, ohne die Partitionen tatsächlich zu erzeugen, das ist bei Beträgen mit 1+ Mio möglichen Partitionen wohl zu langsam.

[Gast]

Nachtrag: Das reicht lange nicht... da fehlen noch ein ganzer Haufen (die niedrige Zahl hatte mich auch schon etwas gewundert). Man kann ja zu jeder Zeit jede Stelle runterzählen... und ich dachte das könne man so einfach umgehen...
Also denk lieber selber nochmal nach.

[Monger]

Ich denke auch: da hilft in erster Linie blanke Gewalt. Du hast X Töpfe (für jede Münzsorte einen) aus dem du eine Münze ziehst. Du legst diese hin, schaust ob du zehn Euro überschreitest (-> ungültig, Schleife auf dieser Ebene abbrechen), unterschreitest (nächste Münze wählen) oder genau triffst (Münzkombination den möglichen Ergebnissen hinzufügen, Schleife auf dieser Ebene abbrechen).

Das ganze rufst du rekursiv für jede Münze auf die du hinlegst.

Mal jetzt so fix in Pseudo Code hingerotzt:


MöglicheMünzen = {1,2, 5, 10, 20, 50, 100, 200}

GelegteMünzen = List<Integer> ' Eventuell ein Stack?!

Ergebnisse = List<List<Integer>>


for each Münze in MöglicheMünzen
Summe = GelegteMünzen.Sum()
select case Summe + Münze
case < 1000 ' diese Schleife nochmal aufrufen
case > 1000 : exit for
case = 1000 : Ergebnisse.Add(GelegteMünzen + Münze), continue for
end for

[patermatrix]

Problem wurde hier (http://www.forum-3dcenter.org/vbulletin/showthread.php?t=470741) auch schonmal diskutiert.

[Trap]

Du legst diese hin, schaust ob du zehn Euro überschreitest (-> ungültig, Schleife auf dieser Ebene abbrechen), unterschreitest (nächste Münze wählen) oder genau triffst (Münzkombination den möglichen Ergebnissen hinzufügen, Schleife auf dieser Ebene abbrechen).

Das ist keine effiziente Lösung für große Ergebnisse, wie lang läuft das wohl, wenn das korrekte Ergebnis UINT_MAX ist...

Für eine effiziente Lösung muss ein wenig Kombinatorik und dynamische Programmierung verwenden.

Edit: Noch ein genauerer Tip:
Man braucht 2 geschachtelte Schleifen, von denen die innere amount*n mal ausgeführt wird.

Edit2: Das stimmt nur für Reihenfolge ist wichtig. Ohne Reihenfolge ist es wohl ein wenig aufwändiger, aber ähnlich.

Noch ein Link zum Thema: http://oeis.org/A073031 ;)
Gibt auch einen Eintrag für die gesuchte Lösung, das wäre aber zu einfach den Link hier zu posten.

[Monger]

Das ist keine effiziente Lösung für große Ergebnisse, wie lang läuft das wohl, wenn das korrekte Ergebnis UINT_MAX ist...

Für eine effiziente Lösung muss ein wenig Kombinatorik und dynamische Programmierung verwenden.
Was ich auch in dem anderen Thread nicht verstanden habe: warum von großen Münzen runter zu kleinen Münzen? Umgekehrt lassen sich alle Wege sofort abbrechen, wenn eine Münze zu groß wird. Das müsste die Anzahl der durchlaufenen Kombinationen schonmal drastisch reduzieren. Gibt natürlich noch jede Menge Grundannahmen die helfen würden. Ist z.B. die Reihenfolge der Münzen egal? Da kann man z.B. beim ziehen einer Münze alle Möglichkeiten auslassen die kleiner als der vorherige Münzwert sind, die sind dann aufgrund von Symmetriegründen nämlich bereits abgedeckt.