Algo durch Caching tunen

[Ashanti]

Hi Vinzenz

IMHO kann man den Algo nochmals rasant beschleunigen wenn man Zwischenergebnisse cachet.

Die rekursive Funktion müsste überprüfen ob sie schonmal mit der gleichen letzten Zwischensumme und Sackfüllung aufgerufen wurde, falls
nein: Anzahl der Folgelösungen berechnen und merken!
ja:   Anzahl der Folgelösungen übernehmen.

Beispiel:

Muenzen/Saecke: 30/6
...
53:   1 2 2 4 6 15  rec:70  ite:53
54:   1 2 2 3 9 13  rec:72  ite:54
55:   1 2 2 3 8 14  rec:73  ite:55
56:   1 2 2 3 7 15  rec:74  ite:56
57:   1 2 2 2 8 15  rec:76  ite:57
...
72:   1 1 3 4 6 15  rec:96  ite:72
73:   1 1 3 3 9 13  rec:98  ite:73
74:   1 1 3 3 8 14  rec:99  ite:74
75:   1 1 3 3 7 15  rec:100 ite:75
76:   1 1 2 5 10 11  rec:103 ite:76

die Teilsequenzen 1 2 2 3 und 1 1 3 3 haben die gleiche Summe
und die gleichen Endzahl, deswegen folgen immer 3 weitere Teillösungen (54-56 = 73-75).

Auf diese Art und Weise verlagert man effektiv Zeitkomplexität
auf Speicherkomplexität :)

Salam
 Ashanti