Design and Analysis of Algorithms

240 Design and Analysis of Algorithms

10.2 EXAMPLE —KNAPSACK PROBLEM

There are n objects numbered i, 0 ≤ i ≤ n − 1, having weights w

i

and contribution to profi t p

i

. There is a sack

having a capacity of M. If a fraction x

i

of the object i is put in the sack, then it increases its weight by w

i

x

i

and

contributes p

i

x

i

to the profi ts. Find the fi lling that maximizes the profi ts.

It is obvious from the problem statement that

we have total wt. = Σw

i

x

i

≤ M ← basic constraint, defi nes feasibility condition;

profi ts = Σp

i

x

i

← to be maximized, optimality requirements;

subject to 0 ≤ x

i

≤ 1, 0 ≤ i ≤ n − 1

We can assume that p and w are positive numbers. ...