next up previous contents
Next: Equipment Replacement Up: A Tutorial on Dynamic Previous: The Knapsack Problem.

An Alternative Formulation

There is another formulation for the knapsack problem. This illustrates how arbitrary our definitions of stages, states, and decisions are. It also points out that there is some flexibility on the rules for dynamic programming. Our definitions required a decision at a stage to take us to the next stage (which we would already have calculated through backwards recursion). In fact, it could take us to any stage we have already calculated. This gives us a bit more flexibility in our calculations.

The recursion I am about to present is a forward recursion. For a knapsack problem, let the stages be indexed by w, the weight filled. The decision is to determine the last item added to bring the weight to w. There is just one state per stage. Let g(w) be the maximum benefit that can be gained from a w pound knapsack. Continuing to use tex2html_wrap_inline1038 and tex2html_wrap_inline1040 as the weight and benefit, respectively, for item j, the following relates g(w) to previously calculated g values:


Intuitively, to fill a w pound knapsack, we must end off by adding some item. If we add item j, we end up with a knapsack of size tex2html_wrap_inline1054 to fill. To illustrate on the above example:

This gives a maximum of 160, which is gained by adding 2 of item 1 and 1 of item 3.

Michael A. Trick
Sun Jun 14 13:05:46 EDT 1998