Fractional Knapsack Greedy — Capacity 100 Kg

Items:
$I_1$:10/15≈0.67, $I_2$:20/25=0.80, $I_3$:30/35≈0.857, $I_4$:40/45≈0.889, $I_5$:50/55≈0.909
Sorted ratio descending: $I_5(0.909), I_4(0.889), I_3(0.857), I_2(0.80), I_1(0.67)$

Fractional Knapsack (optimal via greedy)

Take in ratio order:

• $I_5$:55 → remaining 45, profit 50
• $I_4$:45 → remaining 0, profit +40 =90

Capacity filled exactly 55+45=100. Items $I_5,I_4$ fully taken, others 0. Max profit =90 (fractional = 0/1 same here as no fraction needed).

If capacities differ example where fraction needed: remaining would be filled partially: e.g., if capacity 100 had been 70, would take $I_5$55 + $I_4$15/45 fraction → profit 50+13.33=63.33.

0/1 Knapsack (no fraction) — Greedy not optimal in general

Using 0/1 greedy by ratio, same set $I_5+I_4$ profit90 is feasible. Check alternative subsets weight≤100:

• $I_5+I_3+I_2=55+35+25=115 >100$ no
• $I_5+I_3+I_1=55+35+15=105 >100$
• $I_4+I_3+I_2=45+35+25=105 >100$
• $I_5+I_2+I_1=55+25+15=95 profit 50+20+10=80 <90
• $I_4+I_3+I_1=45+35+15=95 profit90 also 40+30+10=80 <90
• $I_3+I_2+I_1=35+25+15=75 profit60
• $I_5+I_4$ remains best 0/1 for this instance.

Hence greedy coincidentally optimal here, profit 90, weight100 with items $I_5,I_4$ (or alternative $I_5+I_4$). If the question expects demonstrating greedy steps with fractional take, show sorted list and fill; for 0/1 DP optimum also 90.

Note: To illustrate greedy failure for 0/1, classic counterexample: capacity50 items (60,10),(100,20),(120,30) ratio greedy picks 60+100 vs optimal 100+120.

Time $O(n\log n)$ sorting, $O(n)$ selection.