next up previous contents
Next: An Alternative Formulation Up: A Tutorial on Dynamic Previous: Common Characteristics

The Knapsack Problem.

The knapsack problem is a particular type of integer program with just one constraint. Each item that can go into the knapsack has a size and a benefit. The knapsack has a certain capacity. What should go into the knapsack so as to maximize the total benefit? As an example, suppose we have three items as shown in Table 4, and suppose the capacity of the knapsack is 5.

Table 4: Knapsack Items

The stages represent the items: we have three stages j=1,2,3. The state tex2html_wrap_inline1004 at stage j represents the total weight of items j and all following items in the knapsack. The decision at stage j is how many items j to place in the knapsack. Call this value tex2html_wrap_inline892 .

This leads to the following recursive formulas: Let tex2html_wrap_inline1016 be the value of using tex2html_wrap_inline1004 units of capacity for items j and following. Let tex2html_wrap_inline1022 represent the largest integer less than or equal to a.

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