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 and 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 to fill. To illustrate on the above example:

• g(0) = 0
• g(1) = 30 add item 3.
• add item 1.
• add item 1 or 3.
• add item 1.
• add item 1 or 3.

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