Rucksackproblem leichte Erklärung?

...komplette Frage anzeigen

2 Antworten

Du hast Objekte, die jeweils ein gewisses Gewicht haben und eine Zahl, die den Nutzen darstellt. Die Aufgabe ist es nun eine Teilmenge dieser Objekte auszuwählen, die ein gewisses Gesamtgewicht nicht überschreitet (d.h. die gewählten Objekte müssen "in den Rucksack passen") und den Nutzen maximieren.

So weit die Problemstellung. Das Problem ist in gewissem Sinne schwer zu lösen. Es ist kein Algorithmus bekannt, der die optimale Auswahl an Objekten in "vernünftiger" Laufzeit findet. Allgemein geht man davon aus, dass so ein Algorithmus gar nicht existiert, aber das ist bislang unbewiesen (vgl. P-NP-Problem).

Demnach gibt es auch kein Computerprogramm, der das Rucksackproblem löst.

Bei folgendem bin ich mir nicht sicher, aber ich glaube es war so, dass man immer mindestens die Hälfte des optimalen Nutzenwertes erhält, wenn man stets das Objekt mit der besten Nutzendichte nimmt bis der Rucksack voll ist.

Ahaa, zB wenn es viele Objekte wären, dann wären das zu viele Möglichkeiten, die in Frage kommen würde. zB bei 60 objekten wären das irgendwie 1Trillionen Möglichenkeiten(, wenn ich mich nicht irre x)) oder? Wenn ja, dann danke ich dir vielmals!

0
@xVipa

Ja, richtig erkannt :)

Meine Bemerkung, dass man immer mindestens die Hälfte des optimalen Wertes erhalten kann, wenn man immer jeweils das Objekt mit dem bestesn Nutzen-Gewicht-Verhältnis nimmt bis der Rucksack voll ist, ist übrigens richtig, habe noch mal nachgeschaut.

Vermutlich gibt es noch Verfahren um noch näher an die optimale Lösung ranzukommen aber die sind mir nicht bekannt.

1
@xVipa

Man könnte natürlich alle 1 Trillionen Möglichkeiten durchprobieren und sich jeweils die beste Lösung merken. Das dauert aber zu lange, d.h. es gibt zwar einen Algorithmus, aber keinen mit brauchbarer Geschwindigkeit. Da nützt dir dann auch kein schnellerer Computer, wenn nur 10 Objekte dazukommen, muss man 1024 mal so viele Möglichkeiten durchprobieren.

Deshalb gibt man sich mit Näherungslösungen zufrieden.

1

Das Rucksackproblem habe ich vor etwa einem Jahr erfolgreich mit einem genetischen Algorithmus gelöst. Dieser findet nicht immer das Beste Resultat, doch auch wenn der Algorithmus mal daneben liget, ist das Resultat sehr nahe dem Optimum.

Die Idee ist, mit ca 50 zufälligen Packungen zu beginnen (InitialeGenListe). Danach werden die besten gekreutzt (crossOver Beste). Die schlechtesten und Duplikate werden entfernt, sodass wieder 50 Packungen da sind. Die besten bleiben solange erhalten, bis sie übertroffen werden. Nachteil: Man kann natürlich in ein lokales Minimum rutschen, doch das ist immer das leidige am genetischen Algorithmus (Darwin lässt grüßen).

Hier das Hauptprogramm:

void top() {
gegenstandsListe = Gegenstand.liesFile("liste.csv");
erzeugeInitialeGenListe(ANZ_GENE);
for(int k : ord(ANZ_GENERATIONEN)) {
if(DEBUG_OUT)
System.out.println("\nStart (alle auffuellen)\n==========");
else
System.out.print("(" + k + ") ");
alleBisMaxGewichtAuffuellen();
sortAndRemoveDuplicates();
if(DEBUG_OUT)
System.out.println("Cross-Over: ");
loescheSchlechtesteGenstraenge(); // ist ja sortiert, die besten bleiben
crossOverBeste();
removeUebergewichte();
sortAndRemoveDuplicates();
if(DEBUG_OUT)
System.out.println("Mutation der Schlechtesten: ");
mutationSchlechteste();
removeUebergewichte();
sortAndRemoveDuplicates();
}
ausgabeErsteVarianteInListe(ANZ_GENERATIONEN);
}
0

> wieso soll sowas ein Problem sein

Weil es keine Gleichung gibt, mit der sich die Lösung ermitteln lässt. Bisher ist die einzige Möglichkeit, alle Kombinationen durchzuprobieren.

> und gibt es dazu kein Computerprogramm?

Doch, aber das kann auch nur alle Kombinationen durchprobieren. Zum einen ist Ausprobieren nicht gerade das, was sich Mathematiker unter einer Lösung vorstellen. Zum anderen geraten auch schnelle Computer an ihre Grenzen, wenn die Zahl der verfügbaren Gepäckstücke wächst.

Was möchtest Du wissen?