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