5.2 General Knapsack problem: Greedy method is best suited to solve more complex problems such as a knapsack problem. In a knapsack problem there is a knapsack or a container of capacity M n items where, each item i is of weight w_i and is associated with a profit p_i. The problem of knapsack is to fill the available items into the knapsack so that the knapsack gets filled up and yields a maximum profit. If a fraction x_i of object i is placed into the knapsack, then a profit p_ix_i is earned. The constrain is that all chosen objects should sum up to M Illustration Consider a knapsack problem of finding the optimal solution where, M=15, (p1,p2,p3…p7) = (10, 5, 15, 7, 6, 18, 3) and (w1, w2, …., w7) = (2, 3, 5, 7, 1, 4, 1). In order to find the solution, one can follow three different srategies. Strategy 1 : non-increasing profit values Let (a,b,c,d,e,f,g) represent the items with profit (10,5,15,7,6,18,3) then the sequence of objects with non-increasing profit is (f,c,a,d,e,b,g).

Item chosen for inclusion	Quantity of item included	Remaining space in M	PiXi
f	1 full unit	15-4=11	18*1=18
C	1 full unit	11-5=6	15*1=15
A	1 full unit	6-2=4	10*1=10
d	4/7 unit	4-4=0	4/7*7=04

Profit= 47 units The solution set is (1,0,1,4/7,0,1,0).   Strategy 2: non-decreasing weights The sequence of objects with non-decreasing weights is (e,g,a,b,f,c,d).

Item chosen for inclusion	Quantity of item included	Remaining space in M	PiXI
E	1 full unit	15-1=14	6*1=6
G	1 full unit	14-1=13	3*1=3
A	1 full unit	13-2=11	10*1=10
b	1 full unit	11-3=8	5*1=05
f	1 full unit	8-4=4	18*1=18
c	4/5 unit	4-4=0	4/5*15=12

Profit= 54 units The solution set is (1,1,4/5,0,1,1,1). Strategy 2: maximum profit per unit of capacity used

(This means that the objects are considered in decreasing order of the ratio P_i/w_I)

a: P₁/w₁ =10/2 = 5 b: P₂/w₂ =5/3=1.66 c: P₃/w₃ =15/5 = 3

d: P₄/w₄ =7/7=1 e: P₅/w₅ =6/1=6 f: P₆/w₆ =18/4 = 4.5

g: P₇/w₇ =3/1=3

Hence, the sequence is (e,a,f,c,g,b,d)

Item chosen for inclusion	Quantity of item included	Remaining space in M	PiXI
E	1 full unit	15-1=14	6*1=6
A	1 full unit	14-2=12	10*1=10
F	1 full unit	12-4=8	18*1=18
C	1 full unit	8-5=3	15*1=15
g	1 full unit	3-1=2	3*1=3
b	2/3 unit	2-2=0	2/3*5=3.33

Profit= 55.33 units

The solution set is (1,2/3,1,0,1,1,1).

In the above problem it can be observed that, if the sum of all the weights is £ M then all x_i = 1, is an optimal solution. If we assume that the sum of all weights exceeds M, all x_i’s cannot be one. Sometimes it becomes necessary to take a fraction of some items to completely fill the knapsack. This type of knapsack problems is a general knapsack problem.
click here for more details:
http://www.vyomworld.com/gate/cs/ada/5.2.asp