 Postage Stamp Problem |
Erwin Weißnix
unregistriert
 |
|
Meine Frage:
Hallo zusammen,
ich bin auf der Suche nach einer Lösung für das Postage Stamp Problem, genauer gesagt für den Fall, dass 4 Marken auf den Brief geklebt und 8 unterschiedliche Briefmarkenwerte gedruckt werden dürfen.
Kurzfassung des Problems: Aus den 8 unterschiedlichen Werten dürfen maximal 4 Marken (natürlich auch viermal die gleiche) entnommen werden, um von der 1 aufwärts einen möglichst hohen Wert ununterbrochen darstellen zu können. Wäre beispielsweise die Lösung 1, 4, 9, 15, 21, 36, 55, 71, dann könnte ich die 1, 2, und 3 aufkleben, indem ich die 1er Marken benutze. Die 4 könnte ich mit vier 1ern oder einer 4er erzielen, die 5 z.B. durch eine 4er und eine 1er usw. bis irgendwann die Reihe unterbrochen wird - das wäre dann der maximal darstellbare Wert. Ich finde im Netz leider keine Lösung dazu - hat die einer von euch parat bzw. kann sowas programmieren? Ich jedenfalls kann's nicht. :-(
Vielen Dank für eure Hilfe!
Für
Meine Ideen:
leider keine
|
|
16.11.2012 22:41 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
die einfachste Variante ist, alle Kombinationen durchzuprobieren und eine Liste mit den Werten zu erstellen. Diese Liste kannst du dann aufsteigend sortieren und gibst dann die Größte Zahl aus, die in Einerschritten erreichbar ist. Die Anzahl der Kombinationen bei 8 Verschiedenen Werten ist ja durchaus überschaubar und sollte mit einem vernünftigen Rechner in unter einer Sekunde errechenbar sein.
Mach doch mal einen Vorschlag wie du alle Kombinationen erzeugen kannst (Stichwort Backtracking).
VG,
Karlito
|
|
|
16.11.2012 23:01 |
|
|
|
|
Hallo Karlito,
das ist ja gerade mein Problem: Ich kann nicht programmieren und habe noch nicht einmal Software auf dem Rechner, die Entsprechendes umsetzen könnte. Ich bin vor kurzem auf dieses Problem gestoßen und es macht mir einfach Spaß, die Werte dann nachzuvollziehen. Für 2 bis 7 unterschiedliche Briefmarkenwerte ging das ja auch - nur bei 8 finde ich nichts. Hab mich mal im Bekanntenkreis umgehört und die behaupten, das wäre so ein aufwändiger Algorithmus, dass der PC stunden- bis tagelang laufen würde. Würde ich ja auch machen - wenn ich's denn könnte. :-)
|
|
|
17.11.2012 07:13 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
OK. Bei so großen Problemen bin ich auch nicht ganz so fit. Ein Programm dazu schreibe ich dir auf keinen Fall. Dazu fehlt mir die Zeit.
Die Software um Programme zu entwickeln, gibt es wie Sand am Meer (auch kostenfrei). Sollte dich das interessieren, sag bescheid und nenne mir die Programmiersprache, welche du kennst.
Um das Problem zu Lösen, ist es natürlich völlig unmöglich, den gesamten Suchraum zu betrachten. Ich würde hier, mangels besseren Wissens, einen IDA*-Algorithmus wählen und als Distanz zum Ziel den Fehlenden Betrag wählen. Knoten mit negativer Distanz werden verworfen. IDA* ist auch recht einfach zu programmieren.
Ich hoffe das hilft dir.
VG,
Karlito
|
|
|
17.11.2012 14:31 |
|
|
|
