> Teach Dynamic Programming Add-in - Knapsack
 Consider a boy scout packing his knapsack for an overnight camping trip.  He has a set of n items that he can bring.  There are no duplicates and item j weighs an integer amount w(j).  Unfortunately, the total weight of the items that he is considering is greater than the amount W that he can reasonably carry.  To help determine which items to pack, he has assigned a benefit c(j) to item j.  The goal is to maximize total benefit.  In the integer programming chapters, this problem was called the binary knapsack problem because it was modeled using 0-1 decision variables whose individual values corresponded to either selecting or not selecting an item. The boy scout clearly faces a resource allocation problem, so it should be possible to describe his situation in dynamic programming terms. We select this model from the problem definition dialog. The Number of Items and Number of Resources are set here. Also the Problem Name is specified. None of these can be changed after the model is constructed.

For this illustration, we say the boy scout has 15 items from which to choose. The benefit and resource use for each item is shown in the table below. The table is constructed by the add-in to the right of the model. The resource is the weight limitation. and the weights of the items are in the table.

Since this is a binary knapsack problem the maximums are all set to 1. The slack value in cell AF is the value for left-over resources.

Model

The dynamic programming formulation of the problem is below. This is an extract from the DP Models supplement.

The Excel model implements the formulas above with Excel expressions. See the Demo file for the complete model.

Solution

At the top of the worksheet we see a variety of information describing the problem, solution process, interaction and display. The Solve button initiates the dynamic programming solution process.

Clicking the Solve button at the top of the page. For the example we generate all feasible states first and then perform the backward recursion method of dynamic programming. When the complete solution is obtained we use the forward recovery method to return the solution.

The table shows that the value of the optimum knapsack is 57. It is obtained by bringing item 10 and item 12. These two items require the entire weight resource.

Statistics concerning the solution process are in column L. The method generates all states allowed by the feasible states portion of the model plus the single initial state. This totals to 465 states (the reported result includes one additional state). The tree structure used to store the states and related information requires 482 entries. The times for the various portions of the algorithm are also shown.

For the binary knapsack problem with one resource, the number of states grows in proportion to the number of items and the weight limit.

Two Resources

To illustrate a knapsack problem with two resources, we consider the problem below.

The is the same problem considered earlier but with an additional resource. Both resource limits must be satisfied for the optimum solution. The figure shows the strategies adopted for this problem. The exhaustive generation method would require over 900 states, so we have chosen the Forward generation of states. Only states that are reachable from the initial state are generated.

 The model requires an additional state variable. The number of decision variables remains the same. The other aspects of the problem are changed to accommodate the new state definition. See the Demo file for the complete definition. Clicking the Solve button solves the problem. The solution statistics are below. There are 729 reachable states. The optimum solution is below.

Unbounded Knapsack

 When we can bring an unlimited amount of any item, we have an unbounded knapsack problem. The unbounded knapsack problem with one constraint has a single state variable representation similar to a line problem. With multiple constraints there are as many state variables as resources. The dialog on the left asks for the number of items and number of resources. The data structures are like those for the bounded knapsack problem except no maximum number range is provided. Consider a single constraint knapsack problem with right-hand side parameter b = 35.  The values of benefits and weights are given in the table below.  The latter were randomly generated so that no item dominates another.  Although no restrictions are placed on the number of items of each type that can be packed, implicit upper bounds exist due to the weight restriction.

 The model requires as many state variables as resources. The decisions indicate the index of the item to bring. The optimum solution for the example in the table below shows that the knapsack should contain two of item 4 and one of item 5.

Operations Research Models and Methods
Internet
by Paul A. Jensen