Rucksackproblem
Von den Artikeln 
mit den Gewichten 
und den Werten
sind einige so auszuwählen, daß ein Gesamtgewicht 
nicht
überschritten wird.
Die getroffene Auswahl soll einen maximalen Gesamtwert erreichen.
Dieses Problem hängt nicht unmittelbar von der Zeit ab.
Es wird auf folgende Weise ,,künstlich`` dynamisiert.
In jeder Stufe wird eine Entscheidung 
über die Auswahl des Artikels 
getroffen.
Dabei ist für ein ausgewähltes 
,
anderenfalls ist 
.
Wird die zu Beginn einer Stufe noch verfügbare Kapazität mit 
bezeichnet,
dann ergibt sich das folgende dynamische Problem:
 |
(18.118a) |
 |
(18.118b) |
