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!!
3 Antworten
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.
Am Ende der v2-Zeile fehlt eine schließende Klammer :-(
Und max() sollte Math.max() heißen. Du findest bestimmt noch mehr Fehler.
@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.
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!!
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 :-)
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.
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
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?
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.
Okay. Ich überleg mir heute Abend mal, wie es in Java gehen könnte. Vorher komme ich leider nicht dazu.
Wenn man heutzutage noch beigebracht bekommt, dass man globale Variablen verwenden muss, wundert mich einiges nicht mehr.
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.
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.
Die while-Schleife ist falsch — das wird ja durch Rekursion erledigt.
Das Schema:
E.getValue() + backtrackingCalculation(list, capacity-E.getWeight())
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:
Viel Spaß beim Fertigstellen!