Greedy vs Dynamic Programming

Both build an answer from smaller pieces. Greedy commits to one choice and moves on. DP keeps every choice open and picks the best at the end. That single difference decides which one is correct.

Side by side

• Greedy - one path through the choices. Usually O(n log n) for the sort. No extra memory.
• DP - every path, with repeats cached. Usually O(n × m). Needs a table or a cache.
• Greedy is correct only when the local best is provably part of the global best.
• DP is correct whenever the problem has optimal substructure, which is a much weaker requirement.

The same problem, both ways

"Maximum value you can carry within a weight limit." With whole items, greedy fails and DP is needed. Allow fractions of items and greedy becomes correct.

function fractionalKnapsack(items, capacity) {
  // Best value per unit of weight first.
  const sorted = [...items].sort(
    (a, b) => b.value / b.weight - a.value / a.weight
  )

  let total = 0
  let left = capacity

  for (const item of sorted) {
    if (left === 0) break

    const take = Math.min(item.weight, left)
    total += (item.value / item.weight) * take
    left -= take
  }

  return total
}

console.log(fractionalKnapsack([{ value: 60, weight: 10 }, { value: 100, weight: 20 }], 20))

const items = [
  { weight: 10, value: 60 },
  { weight: 20, value: 100 },
  { weight: 30, value: 120 },
]
// capacity 50

// Greedy by value-per-weight takes item 1 (6.0) then item 2 (5.0),
// filling 30 of 50 for a value of 160. It cannot split item 3.
// The best whole-item answer is items 2 and 3: weight 50, value 220.

function knapsack(items, capacity) {
  const best = new Array(capacity + 1).fill(0)

  for (const item of items) {
    for (let c = capacity; c >= item.weight; c--) {
      best[c] = Math.max(best[c], best[c - item.weight] + item.value)
    }
  }

  return best[capacity]
}

console.log(knapsack(items, 50))  // 220

Read the comment in the second example. Greedy is not slightly worse - it is 160 against 220, and it reports its answer with the same confidence.

Deciding in an interview

A practical order that works under pressure:

1. Try greedy first - it is quicker to write and quicker to explain.
2. Spend one minute trying to break it with a counterexample.
3. Found one? Say so out loud and switch to DP. Being able to construct the counterexample is itself a strong signal.
4. Cannot break it? State your greedy argument explicitly, then code it.

"I tried greedy, here is the input where it fails, so this needs DP" is a better answer than jumping straight to a correct DP solution with no reasoning.