Given weight vector {15,25,35,45,55} and the profit vector {10,20,30,40,50} and a knapsack of capacity 100, find atleast three feasible solutions including optimal one for the knapsack problem of 5 items.

Ans

Feasible and optimal solution of knapsack problem:

Gready Approach :


Select items in order of highest profit-to-weight ratio until the knapsack is full.

Profit-to-weight ratios:

  • Item 1: 10/15 ≈ 0.666
  • Item 2: 20/25 = 0.8
  • Item 3: 30/35 ≈ 0.857
  • Item 4: 40/45 ≈ 0.888
  • Item 5: 50/55 ≈ 0.909

Selection Order: 5 → 4 → 3 → 2 → 1

Process:

  • Add Item 5 (55 weight, 50 profit). Remaining capacity: 100 - 55 = 45.
  • Add Item 4 (45 weight, 40 profit). Remaining capacity: 45 - 45 = 0.

Total Weight: 55 + 45 = 100 (feasible)

Total Profit: 50 + 40 = 90



Related Questions