Fractional Knapsack (Greedy) — $W=15$, 7 Items

Obj	1	2	3	4	5	6	7
P	5	10	15	7	8	9	4
W	1	3	5	4	1	3	2
$P/W$	5.00	3.33	3.00	1.75	8.00	3.00	2.00

Step 1 — Sort by ratio descending: 5(8.00), 1(5.00), 2(3.33), 3(3.00), 6(3.00), 7(2.00), 4(1.75)

Step 2 — Greedy selection (fractional allowed):

Step	Item	Weight taken	Cumulative weight	Profit added	Cumulative profit	Remaining
1	5	1	1	8	8	14
2	1	1	2	5	13	13
3	2	3	5	10	23	10
4	3	5	10	15	38	5
5	6	3	13	9	47	2
6	7	2	15	4	51	0
7	4	0 (capacity full)	15	—	51	0

Result (Fractional): Items 5,1,2,3,6,7 fully taken, item4 not taken. Weight=15, Profit=51.

If 0/1 Knapsack (no fraction): Same selection profit 51 is optimal? Check alternatives: Need $O(nW)$ DP to verify 0/1 optimum may be similar but slightly less if fractional part needed. Here all weights fit exactly without fraction, so 51 is also 0/1 optimal (exhaustive check shows no other subset exceeds 51 with weight ≤15). The greedy by ratio happens to be optimal for this instance but not guaranteed in general for 0/1 (counterexample exists).

Why greedy works for fractional: Take highest $p_i/w_i$ first, fill fraction of last item; optimality proved by exchange argument / cut property. Time $O(n\log n)$ for sorting.

Note: If the question expects 0/1 greedy heuristic (not optimal), same steps above would be presented as heuristic; true 0/1 optimum via DP is also 51 here coincidentally.