Find an optimal solution to the knapsack instances n = 7, m = 15

Profit = {10, 5, 15, 7, 6, 18, 3}

Weight = {2, 3, 5, 7, 1, 4, 1}

Given:

n = 4, m = 8, (p1, p2… p4) = (3,5,6,10), (w1, w2… w4) = (2,3,4,5)

To prove: Optimal solution that gives maximum profit.

Proof:

Step 1: (To find profit/ weight ratio)

p1/w1 = 10/2 = 5

p2/w2 = 5/3 = 1.67

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

Step 2: (Arrange this profit/weight ratio in non-increasing order as n values) Since the highest profit/weight ratio is 6. That is p5/w5, so 1st value is 5. Second highest profit/weight ratio is 5. That is p1/w1, so 2nd value is 1. Similarly, calculate such n values and arrange them in non-increasing order.

Order = (5, 1, 6, 3, 7, 2, 4)

Step 3: (To find optimal solution using m = 15 & n = 7)

Consider x5 = 1, profit = 6

Then consider x1 = 1, profit = 10

So weight uptil now = 1 + 2 = 3

Now x6 =1, profit = 18

So total profit = 16 + 18 = 34

And weight uptil now = 3 + 4 =7

Now x3 = 1, profit = 15

So total profit = 34 + 15 = 49

And weight uptil now = 7 + 5 = 12

Now x7 = 1, profit = 3

So total profit = 49 + 3 = 52

And weight uptil now = 12 + 1 = 13

Since m = 15 so we require only 2 units more. Therefore x2 = 2/3

So total profit = 52 + 5 x 2/3 = 52 + 3.33 = 55.3

And weight uptil now = 13 + 3 x 2/3 = 15

Thus, the optimal solution that gives maximum profit is,

(1, 2/3, 1, 0, 1, 1, 1)