Retrieval: greedy or a table?

Two problems rebuilt cold, plus the test that decides which unit a problem belongs to.

Quick check· 5 min

Greedy or table?

You must select items with weights and values to maximize value under a weight limit, where each item may be taken at most once. Is a greedy rule by value-per-weight correct?

No; no exchange argument exists when items are indivisible, and it fails on constructed inputs, so this needs a tableYes; taking the best value per unit of weight first is provably optimalYes, provided the items are sorted by weight firstYes when all weights are equal, and there is no way to tell otherwise

Problem· 18 min

Jump Game II, from scratch

You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.

Problem· 25 min

Edit Distance, from scratch

Greedy

155 / 170

GreedyLesson 9 of 9About 53 min