Kombinatorik - Denkfehler?

[shisha]

[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.

Nun dachte ich mir das gleiche für die 20c
Ich kann wieder aus einer Urne mit 11 Möglichkeiten 2mal ziehen ohne Berücksichtigung der Reihenfolge mit Zurücklegen. Setze ich das Szenario in die Formel ein, erhalte ich

${ 11 + 2 - 1 \choose 2} = 66$

Plus die eine Möglichkeit des 20c-Stückes = 67.

Leider scheint es hier schon zu hapern, das richtige Ergebnis soll 41 sein. Ich kann das leider nicht so schnell nachvollziehen.

[Teil 2]
Eigentlich ist die Aufgabe alle Möglichkeiten des 2€-Stückes zu finden.

Ich habe mit meinem anscheinend falschen Ergebnis gerechnet und versucht alle Möglichkeiten des 50c-Stückes zu finden.

Ich habe zunächst versucht, alle Möglichkeiten zu finden, bei denen Stücke bis maximal 10c verwendet werden.

Das habe ich wieder mit der üblichen Formal gemacht,
n = 11 , k = 5 -> 3003 Mgl

Nun alle mit einem 20c-Stück
Dazu habe ich die obige Formel mit
n = 11, k= 3 -> 286
verwendet,.

Die letzte Möglichkeit ist mit 2 20c-Stücken. Hier sollte es einfach auf die 11 Wege des 10c-Stcükes hinauslaufen.
Addiert man das alles, erhält man (inklsuive der Möglichkeit des 50c-Stückes)
3301 Möglichkeiten.

1€ und 2€ habe ich wieder mit der üblichen Formel, ausgehend vom 50c-Stück hochgerechnet und erhalöte ein riesiges und offensichtlich falsches Ergebnis.

Ich wüsste gerne wo ich den Fehler mache.

[volkard]

Für die Mathematik bin ich leider zu doof.
Aber programmieren konnte ich es.
Vielleicht bringt Dich mein Vorgehen ja auf Ideen, die man in Formeln packen kann.

edit: Code weggemacht. Hier die Ausgabe für Geldmengen bis 99ct.
1 1
2 2
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 11
11 12
12 15
13 16
14 19
15 22
16 25
17 28
18 31
19 34
20 41
21 44
22 51
23 54
24 61
25 68
26 75
27 82
28 89
29 96
30 109
31 116
32 129
33 136
34 149
35 162
36 175
37 188
38 201
39 214
40 236
41 249
42 271
43 284
44 306
45 328
46 350
47 372
48 394
49 416
50 451
51 473
52 508
53 530
54 565
55 600
56 635
57 670
58 705
59 740
60 793
61 828
62 881
63 916
64 969
65 1022
66 1075
67 1128
68 1181
69 1234
70 1311
71 1364
72 1441
73 1494
74 1571
75 1648
76 1725
77 1802
78 1879
79 1956
80 2064
81 2141
82 2249
83 2326
84 2434
85 2542
86 2650
87 2758
88 2866
89 2974
90 3121
91 3229
92 3376
93 3484
94 3631
95 3778
96 3925
97 4072
98 4219
99 4366

[shisha]

Hmm ich habe auch schon einen Fehler gefunden,

Die 10er Kombinationen

2,2,2,2,1,1 + 2,1,1,1,1,1,1,1,1

ergeben zusammen das selbe wie

2,2,2,1en + 2,2,1en

WIe ich das in eine Formel bringen könnte, ist mir noch ein Rätsel.

Deinen Code habe ich nicht weiter betrachtet, da die Aufgabe von Project Euler entstammt und ich sie noch selbst lösen möchte - irgendwann

[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...