The "Knapsack" Problem A hiker has g number of items that he would like to take with him on his next trip. Unfortunately, mot all of the items can fit in his knapsack, so he would have to select the items that have the most "value" to him, and leave the remaining items at home. He can build a chart with the following form to help him:
Item Value Size Volume
Lantern 15 250
Frying pan 12 100
Knife 10 20
Radio 20 400
In this simple case, we assume that the decisions for the items are "mutually independent. That is, deciding to include or exclude some item from the knapsack does not affect the relative of some other item. The objective for the hiker is to find out which items to bring in order to maximize the total value. In an integer programming formulation of the situation, we let n represent the number of items available, numbered 1, 2,... We let B represent the capacity of the knapsack. For item k, we let c aa SB The variable x is set to 1 if item [ is included and to O if it is excluded. The inequality is often referred to represent the value of the item and let a represent the size of the item. The objective is to:
subject to: a1x1+a2x2+a3x3+ anxn 0 SIand integer as a "budget constraint" because space is limited. In an enumerative approach, you solve the problem, total value. Other approaches involve some form of "smart enumeration" ie., find the "optimal solution", by identifying to cut down on the total every subset of items that does not exceed the budget limit and then select the subset having the largest amount of work (computational effort) required to find the optimal solution.