Knapsack — where it appears
Named by 3 essays across 3 fields — each of them below, with the objects they name alongside it.
The same table, filled two ways
Top-down and bottom-up compute identical cells and return identical answers. One of them asks the table half a million questions and recurses four hundred frames deep; the other asks none and recurses none — and on a knapsack it fills twenty-two times as many cells as anything can reach.
The table nobody has to keep
A million-cell table, computed cell for cell in the same order, holding two thousand cells at its peak instead of a million. The saving is exactly (n+1)/2, it costs nothing on any operation counter, and what it buys is paid for with the one thing the table was for.
A table wider than its input
The knapsack table has (n+1)(W+1) cells and is called polynomial. Adding one character to the input doubles it — across four settings the table grows sixty-four times while the input it is written from grows by half.
Named alongside it
The objects these essays reach for when they reach for this one.
Cost modelDynamic programmingMemoisationSubproblemAuxiliary spaceEdit distanceEvaluation orderMeasured countPseudo polynomialTrade offApproximationCache