Informatiker Board | Theoretische Informatik | Ist mein Problem NP-vollständig?

Informatiker Board » Themengebiete » Theoretische Informatik » Ist mein Problem NP-vollständig?

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Ist mein Problem NP-vollständig?

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Mr.Yeah
Grünschnabel

Dabei seit: 19.11.2009
Beiträge: 1

Ist mein Problem NP-vollständig?

Zitatantwort auf diesen Beitrag erstellen

Hallo Leute.

Ich bin kein Ass in Sachen Komplexitätstheorie oder Optimierungsproblemen. Ich habe aber ein praktisches Problem, wovon ich befürchte, dass es NP-vollständig ist.

Ich erkläre mein Problem mit Rucksäcken und Gewichten: Augenzwinkern

Ich habe nur bestimmte Gewichte (d.h. ich habe nur 5-kg- und 10-kg-Gewichte, keine 7-kg-Gewichte). Die Anzahl der Gewichte der jeweiligen Gewichtstypen ist bestimmt.
Nun habe ich Rucksäcke mit verschiedenen Kapazitäten. In der Summe passen die Gewichte genau in die Rucksäcke rein, z.B. habe ich in der Summe genau 510 kg an Gewicht und 510 kg an Kapazität, und es gibt jeweils auf jeden Fall die Möglichkeit, einen Rucksack randvoll zu machen (also einen Rucksack mit der Kapazität von 42 kg gibt's nicht).
Das Problem: Die Anzahl der Gewichte der jeweiligen Rucksäcke sollte möglichst gleich sein. Alle Gewichte müssen auf jeden Fall in Rucksäcken verstaut sein.

Ist das Problem NP-vollständig, oder schlimmer? Wenn ja, wie kriege ich zumindest eine subsuboptimale Lösung hin?

cu
Mr.Yeah

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Mr.Yeah: 19.11.2009 18:27.

19.11.2009 18:27

Nehmen Sie Mr.Yeah in Ihre Freundesliste auf

Herr-Vorragend
unregistriert

Hi,

das hört sich nach eine Variante des klassischen Rucksackproblems an, und das ist NP-vollständig. Es gibt allerdings Approximationsalgorithmen dazu mit bewiesenen Güten, die gar nicht mal soo übel sind, google einfach mal danach.

Gruß

26.11.2009 17:27

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Ist mein Problem NP-vollständig?