Hallo,
erstmal kurz angerissen: ich bin Informatikstudent im 2. Semester. Im Zuge der Vorlesung "Algorithmen und Datenstrukturen" haben wir auch vor Kurzem das Rucksackproblem behandelt. Hier geht es nicht um eine Hausaufgabe, aber ich dachte, meine Überlegung wäre hier trotzdem am Besten aufgehoben.
Meine Überlegung - und damit auch Frage hier - wäre folgende:
Wie füllt man seine Tabelle und liest aus ihr schließlich das optimale Ergebnis, wenn man nicht einen maximalen Wert bei Aufwand <= C sucht, sondern einen minimalen Aufwand bei Wert >= C, also einer Minimumsschranke?
Wozu ich auch noch nichts wirklich gefunden habe, wäre: Wie gebe ich korrekt die für die Lösung verwendeten Gegenstände zurück, statt nur den maximal möglichen Wert and Gegenständen?
Vielleicht kann mir da jemand helfen, vielen Dank schon einmal!
erstmal kurz angerissen: ich bin Informatikstudent im 2. Semester. Im Zuge der Vorlesung "Algorithmen und Datenstrukturen" haben wir auch vor Kurzem das Rucksackproblem behandelt. Hier geht es nicht um eine Hausaufgabe, aber ich dachte, meine Überlegung wäre hier trotzdem am Besten aufgehoben.
Meine Überlegung - und damit auch Frage hier - wäre folgende:
Wie füllt man seine Tabelle und liest aus ihr schließlich das optimale Ergebnis, wenn man nicht einen maximalen Wert bei Aufwand <= C sucht, sondern einen minimalen Aufwand bei Wert >= C, also einer Minimumsschranke?
Wozu ich auch noch nichts wirklich gefunden habe, wäre: Wie gebe ich korrekt die für die Lösung verwendeten Gegenstände zurück, statt nur den maximal möglichen Wert and Gegenständen?
Vielleicht kann mir da jemand helfen, vielen Dank schon einmal!
