Greedy vs DP: The Same Problem, Two Verdicts

"Greedy and dynamic programming are rivals for the same throne. The knapsack problem shows the whole drama: change one rule — can you split an item or not? — and the crown passes from greedy to DP."

The Core Decision

Greedy and DP both build solutions from subproblems, so for any optimization problem you'll often face a fork: can I get away with the fast greedy choice, or must I pay for DP's exhaustive search? The deciding question is whether the greedy-choice property holds — does committing to the locally-best option always keep a globally-optimal solution reachable? If yes, greedy wins (faster, simpler, no table). If a counterexample exists, that greedy rule is invalid. DP may be the right replacement when reusable state and a valid recurrence exist, but other algorithms remain possible. One counterexample disproves that greedy rule; it does not prove DP is the only possible replacement.

The Knapsack: One Rule Flips Everything

The cleanest illustration in all of algorithms. You have a knapsack with a weight limit and items with weights and values:

Fractional knapsack (you may take a fraction of an item): greedy is optimal. Sort by value-per-weight, take the best ratio first, and when the next item doesn't fully fit, take just the fraction that does. Provably optimal — the ratio ordering can't be beaten when you can split.
0/1 knapsack (each item is all-or-nothing): greedy fails, you need DP. Because you can't split, taking the best-ratio item can crowd out a better combination. The fix is the 2D DP from the last track — dp[item][capacity].

Same items, same weights, same goal. The single rule 'can you split?' decides whether the right tool is a one-line greedy sort or a full DP table. That's the paradigm-choice skill in miniature: a tiny change in the problem's constraints can flip which strategy is correct.

Greedy if the greedy-choice property holds (one counterexample disproves it → use DP). DP is the safe, slower fallback that tries all choices. A single constraint can flip the verdict: fractional knapsack is greedy; 0/1 knapsack (no splitting) needs DP. Read the constraints, not just the goal.

The Cost of the Choice

Fractional knapsack takes O(n log n) for sorting, and the sort may use additional space. The O(n·C) integer-capacity DP for 0/1 knapsack is pseudopolynomial in the numeric capacity C. For large C, meet-in-the-middle, approximation, or other methods may fit better.

Pippa's Confession

I learned 'knapsack needs DP' as a flat fact and applied a DP table to a fractional knapsack — total overkill, when a greedy sort solved it in one line. Dad pointed at the constraint I'd ignored: "Can you split an item? Then it's greedy." The same word 'knapsack' had two different right answers depending on one rule. It taught me to read a problem's constraints as carefully as its goal — the constraint, not the goal, often decides the paradigm.

Code

Fractional (greedy) vs 0/1 (DP) knapsack·python

# FRACTIONAL knapsack: greedy is OPTIMAL (you can take a fraction).
def fractional_knapsack(items, capacity):   # items: (value, weight)
    items.sort(key=lambda it: it[0] / it[1], reverse=True)  # best ratio first
    total = 0.0
    for value, weight in items:
        if capacity >= weight:
            total += value; capacity -= weight      # take it whole
        else:
            total += value * (capacity / weight)     # take the fraction that fits
            break
    return total

print(fractional_knapsack([(60,10),(100,20),(120,30)], 50))   # 240.0

# 0/1 knapsack: greedy FAILS (all-or-nothing), so we need DP.
def knapsack_01(items, capacity):           # 2D DP from the last track
    n = len(items)
    dp = [[0]*(capacity+1) for _ in range(n+1)]
    for i in range(1, n+1):
        value, weight = items[i-1]
        for c in range(capacity+1):
            dp[i][c] = dp[i-1][c]                        # skip item i
            if weight <= c:                               # or take it (if it fits)
                dp[i][c] = max(dp[i][c], dp[i-1][c-weight] + value)
    return dp[n][capacity]

print(knapsack_01([(60,10),(100,20),(120,30)], 50))   # 220 — greedy ratio would miss this
# Same items. 'Can you split?' decides: greedy (fractional) vs DP (0/1).

Exercise

Explain why the fractional knapsack is solved optimally by greedy (sort by value/weight) but the 0/1 knapsack is not. Give a concrete tiny example (a few items and a capacity) where the greedy value-per-weight choice is suboptimal for 0/1. Then state the general rule this illustrates about choosing greedy vs DP.

Hint

Fractional: you can always fill the last sliver with the next-best ratio, so highest-ratio-first is provably optimal. 0/1 example: capacity 10, items (value 6, weight 6) and two of (value 5, weight 5) — greedy takes the ratio-1.0 item (6) but two weight-5 items give 10. The rule: greedy needs the greedy-choice property; if a constraint (no splitting) breaks it, use DP.

The Core Decision

The Knapsack: One Rule Flips Everything

The Cost of the Choice

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0