nicht angemeldet
Hallo Daniel,
Das funktioniert allerdings nur bei ganzzahligen Gewichten.
Hm das bringt mich jetzt zum Nachdenken. Ich kann diese Aussage nicht widerlegen, aber mein Gefühl sagt mir, dass die Gewichte auch reelle Größen sein könnten. Also n ist die Anzahl der Gegenstände und m ist die Größe des Rucksacks, die hochiteriert wird. m könnte doch eine Disktretisierung eines von mir aus pi großen Rucksacks sein. Man iteriert über diese Diskretisierung. Die Summe der betrachteten Gegenstände (eine reelle Zahl also) muss <= m sein, damit sie in den Rucksack passen und das ist ja kein Problem.
Also wenn überhaupt, dann müsste der Rucksack und nicht die Gewichte ganzzahling teilbar sein. Kann die Disktretisierung unter Umständen eine optimale Lösung verhindern? Vielleicht muss sie eine Bedingung erfüllen, wie z.B. dass die Schrittlänge zwischen den Größen kleiner sein muss, als das kleinste Gewicht.
Aber mal abgesehen davon, dass es uns Informatikern Spaß macht sich auch die letzten Nuancen zu überlegen, ist für das vom OP gestellte Optimierungsproblem eine centimeterweise Iterierung über die Länge der a-Stangen sicherlich ausreichend. :)
Viele Grüße,
Cruz