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 = …