Ist mein Problem NP-vollständig? |
| 19.11.2009, 18:27 | Auf diesen Beitrag antworten » |
| Mr.Yeah | Ist mein Problem NP-vollständig? 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: 
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 |
|
|
|
| 26.11.2009, 17:27 | Auf diesen Beitrag antworten » |
| Herr-Vorragend | 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ß |
|
|
