nicht angemeldet
Hallo Cruz,
Mit Greedy schon, aber mit der dynamischen Programmierung, ein Verfahren das Hand in Hand mit dem Rucksackproblem gelehrt wird, lässt sich ein Rucksack in O(n^2) packen.
Ah ja, stimmt. Das funktioniert allerdings nur bei ganzzahligen Gewichten.
Das verfahren iteriert ja über die Anzahl der Elemente und die Größe des "Rucksacks". Streng genommen ist das Verfahren also in O(n*m) wobei n die Anzahl der Elemente und m die Größe ist.
Für das Stangenproblem kann man nun einfach in einer ausreichend kleinen Einheit ganzzahlig arbeiten bzw. die Längen (rationale Längen vorausgesetzt, aber dass die nicht rational sein könnten, ist mathematische Spielerei) mit dem Hauptnenner erweitern.
Dieser Hauptnenner kann allerdings exponentiell groß werden:
Beweis: Alle Längen haben als Nenner Primzahlen. Damit ist der Hauptnenner das Produkt dieser Primzahlen, also > 2^n.
Die NP-härte verschwindet also durch die Annahme der Ganzzahligkeit. Bleibt die Frage, ob das Problem ganzzahlig Lösbar ist, oder ob m dabei zu groß wird.
Grüße
Daniel