Frage von karmakommt, 90

Wie programmiere ich das Rucksackproblem rekursiv?

Hallo, ich muss für die Uni ein paar Aufgaben programmieren, die meisten habe ich schon, aber nun muss ich das Rucksackproblem rekursiv lösen und habe einen vorgegebenen Methodenkopf:

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

Im Internet finde ich keine ähnlichen Fälle, da diese immer andere Parameter übergeben dürfen und nun komme ich einfach nicht weiter. Ich sitze schon mehrere Stunden an dieser Methode und habe noch nicht einmal eine Zeile geschafft, da ich keinen Ansatz habe.

Die Liste items, enthält die items die ich benutzen muss. Jedes Item hat einen Wert und ein Gewicht, diese bekomme ich mit getValue und getWeight. Int capacity beschreibt die Menge, die der 'Rucksack' maximal tragen kann. Der Rückgabewert ist vom typ int und soll den Wert (value) enthalten.

Was ich bisher herausgefunden habe ist, dass man jede mögliche Kombination der Items durchgehen muss und immer die bessere Kombination zurückgeben soll, aber ich habe keine ahnung wie ich das machen soll.

Ich muss bis Samstag Abend fertig sein und habe nun schon etliche Internet-Seiten durch, finde aber nichts, was mich weiterbringt.

Vielen Danke schonmal im voraus!!

Antwort
von Mikkey, 71

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.

Kommentar von Mikkey ,

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

Kommentar von karmakommt ,
public static int backtrackingCalculation(List items, int capacity) {

int zaehler = 0;
int result = 0;
if (items.size() > 0) {
for (int i = 0; i < items.size(); i++) {
if (items.get(i).getWeight() <= capacity) {
if (items.get(i).getValue() / items.get(i).getWeight() >= items.get(zaehler).getValue()
/ items.get(zaehler).getWeight()) {
zaehler = i;
}
}
}
if (capacity - items.get(zaehler).getWeight() < 0) {
return result;
}
result = items.get(zaehler).getValue();
capacity = capacity - items.get(zaehler).getWeight();
items.remove(zaehler);

result += backtrackingCalculation(items, capacity);
}

return result;

}

Das habe ich jetzt geschrieben. Wenn ich meine Methode in der main teste, bekomme ich jedesmal richtige Werte heraus, aber wenn ich es abgeben will, sagt mir das Programm, das die getesteten Werte nicht richtig sind. Fällt dir irgendetwas auf?

Antwort
von karmakommt, 31
    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.

Kommentar von ralphdieter ,

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!

Kommentar von ralphdieter ,

Am Ende der v2-Zeile fehlt eine schließende Klammer :-(

Kommentar von ralphdieter ,

Und max() sollte Math.max() heißen. Du findest bestimmt noch mehr Fehler.

Kommentar von KnusperPudding ,

@Ralph: Die Antwort ist wirklich sehr gut. Ich würde dir dennoch dazu raten diese als normale Antwort bei zu steuern, denn diese hätte meiner Meinung nach einen Stern verdient.

Kommentar von karmakommt ,

Vielen vielen Dank!! Es funktioniert!:) Danke für die Mühe den Code zu schreiben und danke dafür, dass du es so toll erklärt und mir auch Fehler gesagt hast. Du kannst diese Antwort gerne nochmal als normale Antwort beisteuern, den Stern hast du dir redlich verdient!!

Kommentar von ralphdieter ,

a) Gern geschehen!

b) Eigentlich habe ich nur Deinen Code kopiert und die drei Fehler verbessert (while⇒if / <⇒≤ / ⇒.add() ). Der Rest ist "Kosmetik".

c) Vor zwei Monaten gab ich meine tausendste Antwort. Mit der nächsten wollte ich warten, bis endlich mal wieder eine gute Frage kommt, die nicht von anderen besser (und schneller) beantwortet werden kann. Deine wär's jetzt gewesen, zumal die anderen Antworten nicht wirklich zielführend sind. Aber bis ich meinen PC eingeschaltet habe, hast Du mir mit Deinem Code schon die halbe Arbeit abgenommen — und meine Faulheit hat gesiegt. Knapp verloren!

Aber was soll's: In ein paar Monaten kommt bestimmt wieder eine klar formulierte, interessante Frage :-)

Antwort
von CarolaA, 57

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.

Kommentar von karmakommt ,

Ich muss es in Java programmieren:)

Kommentar von CarolaA ,

Okay. Ich überleg mir heute Abend mal, wie es in Java gehen könnte. Vorher komme ich leider nicht dazu.

Kommentar von Mikkey ,

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

Kommentar von CarolaA ,

Es wurde uns leider damals so vorgegeben. Und derweil hatte ich noch keine Zeit eine andere Lösung zu suchen.

Kommentar von Mikkey ,

Das geht ja auch nicht gegen Dich, aber man fragt sich, warum sich gescheite Leute über objektorientierte Programmiersprachen die Köpfe zerbrechen, wenn das von Hochschullehrern(!) konterkariert wird.

Kommentar von CarolaA ,

Das denke ich mir auch jedes Mal, aber es gibt Professoren, die lassen sich von Menschen, die schon ewig Programmieren (studiere berufsbegleitend), nichts sagen bzw. lassen sich nicht überzeugen, dass es anders besser wäre.

Ist mir klar, dass es nicht gegen mich geht. 

Kommentar von Orsovai ,

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.

Kommentar von CarolaA ,

Ich lerne im 5.Semester C#, deswegen wundert mich deine Aussage "C# wird eigentlich nicht im Studium gelehrt!"

Kommentar von Mikkey ,

Warum wohl steht "Java" als Thema bei der Frage

Kommentar von CarolaA ,

Sorry, das hab ich überlesen!

Kommentar von Mikkey ,

Es ist letztenendes ja egal, die Anweisungen zum Lösen der Aufgabe dürften eh in C++ und Java fast zeichengleich sein.

Keine passende Antwort gefunden?

Fragen Sie die Community