Rucksackproblem

Von den Artikeln mit den Gewichten und den Werten sind einige so auszuwählen, daß ein Gesamtgewicht W 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 u_j über die Auswahl des Artikels A_j getroffen. Dabei ist für ein ausgewähltes , anderenfalls ist . Wird die zu Beginn einer Stufe noch verfügbare Kapazität mit x_j-1 bezeichnet, dann ergibt sich das folgende dynamische Problem: