Kombinatorik - Denkfehler?
-
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.
-
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
-
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?
-
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.303sMit der direkten Angabe von x(G,2): 0.034s
-
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.
-
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.
-
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).
-
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.
-
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.
-
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.
-
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.
-
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...