The 0/1 Knapsack Problem
Given items with weights and values and a bag that can hold a limited weight, maximise what you carry. The greedy instinct — take the best value-per-kilo first — is provably wrong here, and the reason it fails is exactly what makes the DP table necessary.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int main() {
int wt[4] = {1, 3, 4, 5};
int val[4] = {1, 4, 5, 7};
int n = 4, W = 7;
vector<vector<int> > dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int c = 0; c <= W; c++) {
dp[i][c] = dp[i - 1][c];
if (wt[i - 1] <= c) {
int take = val[i - 1] + dp[i - 1][c - wt[i - 1]];
if (take > dp[i][c]) dp[i][c] = take;
}
}
}
cout << dp[n][W] << endl;
return 0;
}Rows are items and columns are capacities; the answer 9 comes from taking the weight-3 and weight-4 items, not the highest-value one.
How it works, step by step
Every cell is a complete subproblem
dp[i][c] is the best value achievable using only the first i items with capacity exactly c available. Being able to state that sentence precisely is the difference between writing DP and copying it.
The decision is take or skip
For item i you either leave it, inheriting dp[i-1][c], or take it, gaining its value plus the best solution for the remaining capacity using only earlier items. The maximum of those two is the answer for that cell.
Why the recurrence looks back a row
Both branches read from row i-1 because each item may be used at most once. Reading from row i instead would allow the same item to be taken repeatedly, which is the unbounded knapsack — a different problem with a one-character difference in code.
Row 0 and column 0 are the base cases
With no items, or no capacity, the best value is 0. Initialising the vector to zero handles both, which is why the loops can start at 1 with no special cases inside.
Greedy fails because capacity is lumpy
The highest value-per-weight item can leave an awkward remainder that nothing fits into. In this instance the greedy pick blocks a better combination. DP works because it evaluates every capacity split rather than committing to one.
Complexity
One constant-time decision per table cell, which is pseudo-polynomial rather than polynomial — the cost scales with the numeric value of W, so a capacity of one billion is intractable even with only ten items.
Common bugs
Mixing up the item index offset
Row i corresponds to item i-1 in the zero-indexed arrays. Writing wt[i] instead of wt[i-1] reads past the end on the last row and silently shifts every item by one. If your answer is close but consistently wrong, check this first.
Looping capacity forwards in the 1D version
The space-optimised version overwrites a single row in place. Iterating capacity upwards means dp[c - wt] has already been updated for the current item, so the item gets taken more than once and you have accidentally solved unbounded knapsack. The loop must run from W down to wt[i].
Reading dp[i][c - wt] instead of dp[i - 1][c - wt]
This is the same bug in the 2D table: it permits reusing the current item. The result is always at least as large as the correct answer, so it looks like an improvement rather than an error. Stepping through the table and checking which row a cell was read from settles it.
Assuming greedy by value density works
Sorting by value per unit weight and taking greedily is correct for fractional knapsack, where items can be split, and wrong for 0/1. The failure is not an edge case — it happens on small ordinary inputs like this one — and no tie-breaking rule fixes it.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
What does dp[i][c] mean in the knapsack problem?
The maximum total value obtainable using only the first i items with a capacity of c. Each cell is a self-contained answer to a smaller version of the same question, which is why the table can be filled row by row using only previously computed cells.
Why can't you solve 0/1 knapsack greedily?
Because taking the item with the best value-to-weight ratio can leave a capacity remainder that nothing fits into, blocking a better combination. Greedy is correct only for fractional knapsack, where you can take part of an item and any leftover capacity is always usable.
Why does the 1D knapsack loop go backwards?
Because the space-optimised version reuses one array for both the previous and current item rows. Iterating capacity downwards guarantees that dp[c - weight] still holds the previous item's value when you read it. Going forwards reads an already-updated cell, which lets the same item be taken repeatedly.
Is knapsack really polynomial time?
It is pseudo-polynomial. The O(n * W) cost is linear in the numeric value of the capacity, not in the number of bits used to write it down, so doubling the bit-length of W squares the runtime. That is why 0/1 knapsack is NP-hard despite having a table-filling algorithm that looks efficient.