Hey,
Bin gerade dabei einen Algo zu schreiben der mir für eine imaginäre Währung, die nur aus Münzen besteht eine optimale Stückelung errechnet.
folgendes ist gegeben:
N .... Anzahl der verschiedenen Münzen in der Währung
S .... Anzahl der Münzen pro Bürger
(beides ist variabel)
der Algo sollte nun folgenden Erwartungen entsprechen:
=>es sollte eine Stückelung gefunden werden, die einen möglichst hohen Wert (MAX) mit den S Münzen legbar macht. Weiters sollte jeder Wert zw. 1 und dem MAX-Wert mit den S Münzen legbar sein.
mein erster Ansatz ist nun folgender:
Eine rekursive Funktion schreiben, die als Übergabeparameter von 1..n gefütter wird. In jedem Durchlauf wird gecheckt ob die beiden Erwartungen erfüllt werden. Danach den Übergabeparamter inkrementieren. Sollte die Funktion negativ terminieren, so heißt das, dass der letzte benutze Wert des Übergabeparameters dem gesuchten MAX für diese Stückelung entsprochen hat. (diese sollte durch den Backtracking Algo implementiert sein)
Darüber müsste ich etwas stülpen, dass die verschiedensten Stückelungen durchpermutiert und dann jeweils die rekursive Funktion aufruft, die die Stückelung dann überprüft.
Am Ende alle MAX Wert vergleichen und den höchsten Wert mit der zugeordneten Stückelung liefern.
========================================================
So nachdem wir eh schon die Finger abfallen - hat jemand von euch Erfahrung mit der "Standard Exhaustionsvariante" ?? - der Rest ist dann eher trivial.
Wäre über jeglichen Input sehr dankbar.
mfg.