6.knapsack problem

6. Find an optimal solution to the knapsack problem n=7, M=15,
(p1, p2, p3, p4, p5, p6, p7) = (10, 5, 15, 7, 6, 18, 3),
(w1, w2, w3, w4, w5, w6, w7) = (2, 3, 5, 7, 1, 4, 1)
Solution:
Case-1: maximum profit

X6=1, x3=1, x1=1, x4=4/7, x5=0, x2=0, x7=0

∑ Pi Xi= p1x1+p2x2+p3x3+ p4x4+p5x5+p6x6+p7x7
=10*1+5*0+15*1+7*4/7+6*0+18*1+3*0
=10+15+4+18
=47

Case-2: Minimum weight

X7=1, x5=1,x1=1,x2=1, x6=1, x3=4/5,x4=0

∑PiXi=p1x1+p2x2+p3x3+p4x4+p5x5+p6x6+p7x7
=10*1+5*1+15*4/5+7*0+6*1+18*1+3*1
=10+5+12+6+18+3
=54

Case-3: Maximum profit per unit weight

P1/w1=10/2=5
P2/w2=5/3=1.6
P3/w3=15/5=3
P4/w4=7/7= 1
P5/w5=6/1=6
P6/w6=18/4=4.5
P7/w7=3/1=3
X5=1, x1=1, x6=1, x3=1, x7=1, x2=2/3, x4=0


∑PiXi = p1x1+p2x2+p3x3+ p4x4+p5x5+p6x6+p7x7
= 10*1+5*2/3+15*1+7*0+6*1+18*1+3*1
=10+3.3+15+0+6+18+3
=55.3


The Three feasible solutions .are:

(x1,x2,x3,x4,x5,x6,x7) ∑wixi ∑ pixi
1. ( 1, 0, 1, 4/7, 0, 1, 0) 15 47
2. (1, 1, 4/5, 0, 1, 1, 1) 15 54
3. (1, 2/3, 1, 0, 1, 1, 1) 15 55.33

The optimal solution is maximum profit is 55.33 and the inputs are (1,2/3,1,0,1,1,1)