Kombinatorik - Denkfehler?

[CStoll]

shisha schrieb:

[Teil 1]
Hallo, ich möchte (für den Anfang) wissen, auf wie viele Arten man 20 Cent ausgeben kann (alle Münzen und jede Anzahl an Münzen erlaubt)

Bis zu 5 Cent ist das noch sehr einfach und kann aufgemalt werden

5
2 2 1
2 1 1 1
1 1 1 1 1
_______________
4 Möglichkeiten

Für 10 Cent habe ich dann folgendes gedacht:

Ich kann 10 Cent aus 2 mal 5 Cent aufbauen. Alle verschiedenen Möglichkeiten erhalte ich wenn ich das Modell "Ziehen aus einer Urne mit Zurücklegen ohne Beachtung der Reihenfolge" hernehme.

Die Dazu passende Formel ist dann

${n + k - 1 \choose k}$

Hier habe ich dann sämtliche Möglichkeiten die 10 mit den Münzen 1,2 und 5c zu erzeugen. Dazu muss ich noch die 1 Möglichkeit des 10c -Stückes rechnen.

Das Ergebnis, das ich hierbei erhalte ist 11.
Soweit hab ich es auch mal mit Stift und Zettel überprüft, scheint zu stimmen.

Schon bei diesem Ansatz hast du einen Denkfehler drin: Die Kombination 5 2-Cent-Münzen erfasst du bei der Zerlegung nicht, dafür sind andere Kombinationen mehrfach enthalten.

[guter Tipp]

Probiers mal mit erzeugenden Funktionen. Für den Fall, dass man Münzen von jedem natürlichen Betrag verwenden kann, siehe http://en.wikipedia.org/wiki/Partition_function_(number_theory)#Partition_function

[shisha]

Danke für die Vorschläge bisher, ich denke mal dass es ok ist und im Sinne von ProjectEuler, wenn ich mir Denkanstösse von ausserhalb hole.

[Jester]

Mein Tipp:

Sei x(G,M) die Anzahl an Möglichkeiten, wie man Geldmenge G zerlegen kann, wenn die größte erlaubte münze wert M hat.

Kennst Du x(G,1)?

Kannst Du x(G,M) durch x(G',M'), wobei G'<G oder M'<M ist, auszudrücken (evtl. auch als summe von mehreren von denen)?

Das würde gewaltig weiterhelfen.

[knivil]

Sieht aus wie Euler 31, haettest am Anfang auch gleich sagen koennen. Denk nicht zu kompliziert, eine Loesung mit geschachtelten Schleifen sollte genuegen. Ja es gibt schnellere Algorithmen, aber ..

Edit Code entfernt.

Wenn man anstatt der 200 eine 1000000 ansetzt, dann gibt es 99'341'140'660'285'639'188'927'260'001 (~ 99 * 10^27) Moeglichkeiten. Jedoch ist eine Loesung mit Schleifen dafuer nicht mehr effizient genug.

[volkard]

knivil schrieb:

eine Loesung mit geschachtelten Schleifen sollte genuegen

Oh, mir kam nur eine rekursive in den Sinn, und wie die von Jester, nur daß ich mit x(0,M) statt wie er mit x(G,1) abgebrochen habe.
Schick mir mal Deine Schleifenlösung an volkard@normannia.de

[Jester]

volkard schrieb:

Oh, mir kam nur eine rekursive in den Sinn, und wie die von Jester, nur daß ich mit x(0,M) statt wie er mit x(G,1) abgebrochen habe.

die du aber hoffentlich nicht stumpf rekursiv hingeschrieben hast?

[volkard]

Jester schrieb:

volkard schrieb:

Oh, mir kam nur eine rekursive in den Sinn, und wie die von Jester, nur daß ich mit x(0,M) statt wie er mit x(G,1) abgebrochen habe.

die du aber hoffentlich nicht stumpf rekursiv hingeschrieben hast?

Doch. Ich wollte nur eine Rechenweise finden und hatte keine Lust, die Beispiele per Hand zu überprüfen. Bis G=200 braucht es nur Sekündchen. Aber 10€ sind schon utopisch viel für mein Programm. Es drängt sich auch keine Optimierung in mein Auge.

Oh, da ist ja schon eine.
Rechenzeit mit:
- nur meiner Abbruchbedingung: 13,972s
- auch Deiner Abbruchbedingungen: 0.303s

Mit der direkten Angabe von x(G,2): 0.034s

[Jester]

Und jetzt noch die Tabelle x[G,M] bauen, statt alles stumpf mehrmals zu berechnen?

edit: damit müßten alle varianten in etwa vergleichbar werden.

[volkard]

Jester schrieb:

Und jetzt noch die Tabelle x[G,M] bauen, statt alles stumpf mehrmals zu berechnen?

Für Bereiche, die vorher noch utopisch waren, wie 50€:
instant.

100000€ in 8s (Überlauffehler im Ergebnis ignoriert). Bei mehr geht langsam der Speicher aus.
Verwendet habe ich eine map<pair<int,int>,int> als cache.

[volkard]

Jester schrieb:

Und jetzt noch die Tabelle x[G,M] bauen, statt alles stumpf mehrmals zu berechnen?

Ich hatte nur gecached, memoization.
Tabelle von unten aufbauen?
Oder gar lineare Programmierung, geht das hier (da bin ich ein wenig ungeübt).

[Jester]

Ich würde ja einfach ne Tabelle x[G,M] bauen, dabei M natürlich nicht als echten Münzwert sondern nur als index in ein Array wert[M], wo dann der echte wert drinsteht; damit kann ich dann die münzen von 0 bis anzahl münzen/scheine-1 numerieren. für alle münzen+scheine die es im euroland gibt brauch ich dann also wieviele spalten in der tabelle?

in cent: 1,2,5,10,20,50,100,200,500,1000,2000,5000,10000,20000,50000

15 stück, wenn ich nix vergessen hab. das macht einen speicherbedarf von ca. 15* centbetrag, den ich zerlegen mag. Da dürfte der Speicher so schnell eigentlich nicht ausgehen.

[Jester]

volkard schrieb:

Oder gar lineare Programmierung, geht das hier (da bin ich ein wenig ungeübt).

du meinst dynamische programierung, genau das ist es. Man kann die Tabelle einfach von unten her ausfüllen (oder eben rekursiv von oben her und zellen, die als noch nicht korrekt befüllt markiert sind (z.b. mit -1) rekursiv mit dem richtigen wert füllen.

von unten hoch ist aber der klassische weg bei dynamischer programmierung.

[volkard]

Jester schrieb:

das macht einen speicherbedarf von ca. 15* centbetrag, den ich zerlegen mag. Da dürfte der Speicher so schnell eigentlich nicht ausgehen.

Ich denke, es war nur der Stack-Speicher, der ausging.

[volkard]

Jester schrieb:

du meinst dynamische programierung

Ja, klar. Wort nicht gefunden, peinlich.

Jester schrieb:

von unten hoch ist aber der klassische weg bei dynamischer programmierung.

Die Frage ist, ob man sich die ganze Tabelle sparen kann, und auf nur einer oder zwei Zeilen arbeiten kann.

[Jester]

Hm, sagen wir, wir wollen die einträge x[G,M_max] ausrechen (M_max ist die nummer der größten münze und W_max ihr wert). Offensichtlich braucht man dazu x[G,M] für alle M<=M_max, da darf man also nix weglassen. Allerdings braucht man im schlimmsten Fall nur x[G-W_max,M_max]. Alle Einträge x[G',M'] mit G' < G-M_max sind somit für die Berechnung von x[G,M_max] irrelevant und können vergessen werden.

Theoretisch müßtest Du also ein Array mit größe x[W_max,M_max] zyklisch benutzen können... viel spaß beim coden.

Mit viel weniger wird man aber wohl nicht auskommen.
edit: und jetzt hör bitte auf mich vom arbeiten abzuhalten...