nicht angemeldet
Hallo Cruz,
Naja, das Problem "Kann der Rucksack so gepackt werden, dass ein Nutzen >= x erreicht wird" ist erwiesener maßen NP-Hart.
Das Optimierungsproblem "Berechne den größten Nutzen" kann man ja ganz trivial in das Entscheidungsproblem umbauen. Man Optimiert einfach, und guckt ob es reicht.
Nun haben wir einen Algorithmus, der das Problem in O(n^2) löst.
Es gibt also zwei Möglichkeiten:
1. der Algorithmus funktioniert nur für eine eingeschränkte Variante des Problems
2. Wir haben einen Beweis für P = NP gefunden (möglich, aber unwahrscheinlich, vor allem da der Algorithmus schon lange bekannt ist ;)
Also wenn überhaupt, dann müsste der Rucksack und nicht die Gewichte ganzzahling teilbar sein.
Wenn man den Algorithmus sieht, wird da eine n x B Matrix (B ist die Schranke Größe) aufgebaut, also muss B schonmal ganzzahlig sein.
Die Größe der Elemente w(i) wird allerdings verwendet, um auf Einträge dieser Matrix zuzugreifen. Muss also auch ganzzahlig sein.
Man kann sich nun natürlich überlegen, ob man an der ein oder anderen Stelle vielleicht runden oder sonstwie rumtricksen könnte, aber wenn man den Algorithmus so anwenden will, wie er da steht, muss man irgendwie ganze Zahlen bekommen.
Das erreicht man, indem man sich ein Raster wählt, in das sowohl B also auch alle w(i) reinpassen, und letzteres ist entscheidend.
Damit braucht man ein Raster von einer Größe, die durch alle Nenner teilbar ist und das ist dann eben exponentiell groß.
Ich sehe an dieser Argumentation (natürlich ist es kein Beweis, dass es nicht geht, der dürfte schwierig sein) auf den ersten Blick keine Schwäche.
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.
Wie diskretisierst Du die Gewichte? Runden? Die Fehler schaukeln leicht so auf, dass eine andere, oder gar eine unmögliche Lösung optimal wird:
Gewichte: 4 x 1/3
Maximale Länge: 1
Schrittweite: 1/4 (sieht also kein genug aus)
Es werden allso alle Gewichte gerundet auf 1/4. Und schon passen alle Elemente rein.
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. :)
Naja, hm 1 m minimale Elementlänge, 50 m Gesamtlänge. Dann würdest Du also Größenordnungsmäßig 50 * 5000 = 250000 Schritte machen. Geht sicher noch, elegant ist das aber nicht und die Lösung ist noch nicht mal exakt, wenn er nicht sowieso nur mit cm-Genauigkeit arbeiten will.
Besser als alle Kombinationen durchzuprobieren, ist der Ansatz natürlich noch und an ein heuristisches Verfahren kommt man damit sicher auch locker ran.
Grüße
Daniel