Zitat von
Thorben_K:
wie das geht weiss ich leider nichts, aber das ist das sogenannte "[
dp]Rucksack probleme"[/
dp], da habe ich vor einigen tagen erst ein lösungs ansatz bzw vorschlag gesehen
Das wäre aber eine sehr sehr spezielle Variante des Rucksackproblems. Immerhin soll hier ein exakter Wert erreicht werden. Beim Rucksackproblem handelt es sich vielmehr um ein Optimierungsproblem (einer der Fälle, in dem man nur das Beste sucht).
Selbst im speziellen Fall, dass das Gewicht dem Wert gleicht kann es sein, dass die optimale Lösung nicht das volle Gewicht ausnutzt. Sagen wir man hat ein max. Gewicht von 3 und zwei Teile, die gerade 2 wiegen (und den gleichen Wert haben!).
Natürlich kann man auch das spezielle Rucksack-Problem (bei dem halt Gewicht = Wert) ist verwenden, es lösen und wenn das max. Gewicht hier dem halben Erbe und die Lösung des Rucksackproblems als Wert halt auch dem halben Erbe entspricht, super dann hat man eine Lösung. Wäre allerdings eine vollkommen unnötige Reduktion (auf ein imo nicht gerade leichteres Problem). Durchaus möglich, aber eben mehr arbeit