The “knapsack problem” has a long history in operations research. The traditional version has a hiker getting ready to go camping, and she needs to determine which items to carry in her knapsack. Each item has a weight and a subjective value. There’s a limit on the number of pounds that she can carry. Which items should she take? The table for this problem presents potential items for the camping trip, how much they weigh, and a value for each on a scale from 1 to 10, with 10 being best. The hiker only wants to carry at most 18 pounds in her knapsack.

The knapsack problem has number of other applications whenever there is a choice of options, each of which has a cost and a value. This includes certain portfolio selection problems such as the Simkin and Steinberg example in section 6.3 with only the investment limit constraint.

(a) Formulate the binary program to solve this problem, and find the optimal solution using Excel. Is there anything odd about the solution? What constraint probably needs to be added?

(b) A common heuristic (or “rule-of-thumb”) for knapsack-like problems is to take the ratio of value ÷ cost for each item and then place each item in the knapsack until the knapsack is full. Try that heuristic on this problem. How does it compare with the optimal solution?

Transcribed Image Text:

ITEM WEIGHT (pounds) VALUE Machete 2 8 Junk food 10 7 Healthy food Cooking equipment 12 8. Charcoal 4 6 Water 3 10 Textbook for studying 5 5 Laptop computer 3 Toiletries 3 5 6.