0/1 Knapsack - Why Greedy Fails

You might think: "Just sort by value and grab items until the bag is full." Try it on this example: Items: ($weight=1$, $value=1$), ($weight=3$, $value=4$), ($weight=4$, $value=5$), ($weight=5$, $value=7$).

Capacity $W = 7$. Greedy by value picks the most valuable item first: ($weight=5$, $value=7$). Remaining capacity is 2. The only item that fits is ($weight=1$, $value=1$). Total value: $7 + 1 = 8$.

But taking items ($weight=3$, $value=4$) and ($weight=4$, $value=5$) gives $4 + 5 = 9$ with total weight $3 + 4 = 7$. The greedy approach misses this better combination. You need DP to explore all possibilities efficiently.