|
 |
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.
 |
|
| |
|
| |
|
| |
|
