A knapsack with capacity b must be filled, with no spare capacity,
so as to maximize the value of the contents. There are n types of item to
place in the knapsack, where each item of type i consumes space ai and
adds value ci. Any (integral) number of items of each type may be selected.
First write a dynamic programming recursion that defines f(i, si) for stages
i = 1,...,n + 1. Then write a different recursion that dispenses with stages
and defines f(s) for each state s. The control decision in each state (except
s = b) is which type of item to add to the knapsack (only one type, and only
one item of that type). The state transitions must end up in state b, which
means that f(b) = 0, and there are no available controls in state b. This
formulates the problem as a deterministic finite automaton (Section 6.12.1).