Knapsack Problems
Juan Hernandez, a Cuban athlete who visits the Unite States
and Europe frequently, is allowed to return with a limited number of consumer
items not generally available in Cuba. The items, which are carried in a duffle
bag, cannot exceed a weight of 5 pounds. Once Juan is in Cuba, he sells the
items at highly inflated prices. The three most popular items in Cuba are denim
jeans, CD players, and CDs of U.S. rock groups. The weight and profit (in U.S.
dollars) of each items are as follows.
Items Weight (lb) Profit ($)
1. Denim jeans 2 90
2. CD players 3 150
3. Compact discs 2 30
Juan wants to determine the combination of items he should
pack in his duffel bag that will maximize his profit. The problem is an example
of a type of integer programming known as a “knapsack” problem.
Formulate and solve this problem.
