The Knapsack Problem

ICMS

Page:

Demo

THE KNAPSACK PROBLEM

Robin Hood, the Prince of Thieves, had all of Nottingham puzzled. After single-handedly breaking into the castles treasure vault, he made away with an assortment of precious statuettes and ceremonial cups, but only one of the eight antique Beelzebub menhirs! The knapsack he was seen to be carrying could easily have held two. The menhirs were the most precious of the treasures and many a buyer would have paid handsomely for more. The robbery, apart from ruining the sheriffs career, left a deep scar on his mind; and legend has it that the sheriff of Nottingham, soliloquising on his deathbed had but one thing to say,

"Why one? Why only one?"

The above problem is one of optimal allocation of resources. Such problems fall under the class of what is mathematically known as the knapsack problem:

Fill a given knapsack of a fixed capacity with various objects of different weights and utility values, such that the profit is maximised.

The obvious solutions of taking as many as possible of the objects with the maximum utility value or those with the maximum value per unit weight do not necessarily give the optimal solution.

When Robin Hood broke into the vault, he found menhirs (each weighing 6 kg and each worth 480 sovereigns), statuettes (2 kg; 158 sovereigns), silver cups (3 kg; 233 sovereigns) and silver bars (1 kg; 2 sovereigns). His knapsack had a capacity of 13 kg. He could have taken two menhirs and filled up the space left in his knapsack with 1 silver bar. He would then have made a profit of 962 sovereigns. Robin Hood, in fact, made a profit of 1029 sovereigns by taking only one menhir, two statuettes and one silver cup.

Mathematically, the knapsack problem can be stated as:

Maximize å v_j(d_j)

subject to å d_jw_j £ W

where d_j = number of the j^th object included;

v_j (d_j) = utility of d_j objects of the j^th type of object;

w_j = weight of the j^th object;

and W = capacity of the knapsack.

Problems of this class naturally arise in many fields like capital budgeting, cutting stock, time scheduling, cargo loading, etc.