A knapsack problem
Suppose a 10-lb knapsack is to be filled with three types of items
(item 1: b1=4lb, w1=$11, item 2: b2=3lb, w2=$7, item 3:
b3=5lb, w3=$12).
To maximize
total benefit, how should the knapsack be filled ?
Define g(w) to be the maximum benefit that can be gained from w-lb
knapsack. Then
g(w) = |
max
j=1,2,3
|
{ bj + g(w-wj) }. |
|
|