Wie programmiere ich das Rucksackproblem rekursiv?

...komplette Frage anzeigen

3 Antworten

Hallihallo!

Das Rucksack-Problem ist eindeutig ein Lieblingsbeispiel viele Professoren.

Ich habe diese Aufgabe erst letztes Semester gehabt. Ich habe das in C++ programmiert, in welcher Sprache musst du es programmieren?

Auf jede Fälle brauchst du globale Variablen, die deine optimale Kombination speichert + den optimalen Totalwert des Rucksacks. Und die gegebene Funktion musst du dann innerhalb deiner Funktion nochmals aufrufen (rekursiv) und das solange bis entweder eine Kombination gefunden wurde oder neu angefangen werden muss.

Liebe Grüße, CarolaA.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von karmakommt
24.08.2016, 14:23

Ich muss es in Java programmieren:)

0
Kommentar von Mikkey
24.08.2016, 14:23

Wenn man heutzutage noch beigebracht bekommt, dass man globale Variablen verwenden muss, wundert mich einiges nicht mehr.

2
Kommentar von Orsovai
24.08.2016, 14:23

Der generische Typ List lässt mich auf C# oder Java schließen. Da C# eigentlich nicht im Studium gelehrt wird, nehme ich an, es handelt sich um Java.

1

Ansatz:

Du nimmst aus der Liste das schwerste Stück heraus, das noch passt und rufst die Funktion mit der geänderten Liste und der um dieses Gewicht verminderten Capacity auf.

Existiert kein passendes Stück, kehrst Du direkt zurück.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Mikkey
24.08.2016, 14:20

Ergänzung (ich habe aus dem Namen auf ein anderes Problem geschlossen):

Du nimmst nicht das schwerste Stück sondern das mit dem besten Verhältnis Wert/Gewicht

1
    public static int backtrackingCalculation(List items, int capacity) {

int with = 0;
int without = 0;
int capa = capacity;

while (items.size() > 0) {

if (items.get(0).getWeight() < capacity) {
with += items.get(0).getValue();
capacity -= items.get(0).getWeight();
items.remove(0);
with += backtrackingCalculation(items, capacity);
without += backtrackingCalculation(items, capa);
} else {
items.remove(0);
with+= backtrackingCalculation(items, capacity);
without += backtrackingCalculation(items, capa);
}

}

if (without > with) {
return without;
}
return with;

}

Habe eine neue Variante. Ich habe versucht jede mögliche Kombination durchrechnen zu lassen und die Beste dann auszusuchen.

with bedeutet ich nehme das item mit rein und without bedeutet ich nehme es nicht mit rein.

Aber auch das funktioniert nicht. Es berechnet zwar einiges aber das richtige Ergebnis wird auch nicht gefunden.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von ralphdieter
25.08.2016, 11:38

Die while-Schleife ist falsch — das wird ja durch Rekursion erledigt.

Das Schema:

  • ist die Liste leer, gib 0 zurück.
  • sonst: nimm irgendein Element E aus der Liste heraus und untersuche zwei Fälle:
  • E kommt in den Rucksack: Der Wert ('with') ist dann
    E.getValue() + backtrackingCalculation(list, capacity-E.getWeight())
  • E bleibt draußen: Der Wert ('without') ist dann
    backtrackingCalculation(list, capacity)

Der bessere dieser beiden Werte wird zurückgegeben.

Anmerkungen:

Der Suchbaum berechnet prinzipiell alle Teilmengen von items. An der Spitze steht items[0] mit den Zweigen drin/draußen, darunter jeweils items[1] usw. Von diesem Baum werden nur die drin-Zweige gekappt, die die Kapazität überschreiten. Von daher ist es wohl fast egal, in welcher Reihenfolge die Elemente abgearbeitet werden.

Ich würde immer das letzte Element der Liste nehmen und es dem Aufrufer überlassen, seine Eingangsliste "geeignet" zu sortieren. So kann man die Laufzeit bei verschiedenen Sortierungen leichter vergleichen.

Dein Algorithmus vereinfacht sich nun etwas:

public static int backtrackingCalculation(List<Elem> items, int capacity) {

int value = 0;

if (items.size() > 0) {

// Ein Element temporär entfernen:
Elem e = items.remove(items.size()-1);

// Wert ohne e:
 value = backtrackingCalculation(items, capacity);

// Wert mit e:
 if (e.getWeight() <= capacity) {
int v2 = e.getValue()+backtrackingCalculation(items, capacity-e.getWeight();
value = max(value, v2);
}
// Temporäres Entfernen reparieren:
items.add(e);
}

return value;
}

Viel Spaß beim Fertigstellen!

2

Was möchtest Du wissen?