Hard · DP

0/1 Knapsack

You have seen this table before: best[c] = best answer with capacity c. Coin change filled it top-down because each coin had unlimited supply; here each item exists once, and that single fact flips the inner loop from forward to backward. One loop direction is the difference between renting and owning.

At a glance<code>best[c] = max value with capacity c</code>; per item, loop c from W <em>down</em> to w: <code>best[c] = max(best[c], best[c-w] + v)</code>. Backward = each item once.

Problem

Input: The first line has n and W (1 ≤ n ≤ 20, 1 ≤ W ≤ 1000). Then n lines: w v, the item's weight (1 ≤ w ≤ 1000) and value (1 ≤ v ≤ 1000).

Output: The maximum total value achievable with total weight ≤ W, taking each item at most once.

Samples:

Input	Output
`1 6 3 5`	`5`
`3 5 2 3 3 4 4 5`	`7`

The first sample is the reuse detector: one item of weight 3 and value 5 in a bag of 6. Taking it twice would give 10 — the correct answer is 5, and only the backward loop gets it right.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Why backward, in one sentence

best[c-w] + v must mean "best without this item". Sweeping c downward, every best[c-w] you read is still from the previous item's row — untouched, so the item cannot be counted twice. Sweeping upward, best[c-w] was already updated this round: the item sneaks in twice, and the first sample (answer 10 instead of 5) catches it.

Hint 2 — Zero the table yourself

best is global, and on this engine global arrays are not auto-zeroed (the lesson from Matrix Multiplication). One loop: for (c = 0; c <= W; c++) best[c] = 0;. Empty capacity legitimately holds value 0 — that base case is what the whole table grows from.

Hint 3 — Items that do not fit

An item heavier than W is legal input and must simply be skipped — the backward loop from W down to w[i] does this automatically, because the loop body never runs when w[i] > W. Resist the urge to filter the input; the loop bounds already are the filter.

Solution (try it first!)

#include <iostream>
using namespace std;

int best[1005];

int main() {
    int n, W;
    cin >> n >> W;
    int w[20], v[20];
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];

    for (int c = 0; c <= W; c++) best[c] = 0;

    for (int i = 0; i < n; i++) {
        for (int c = W; c >= w[i]; c--) {
            if (best[c - w[i]] + v[i] > best[c]) {
                best[c] = best[c - w[i]] + v[i];
            }
        }
    }

    cout << best[W] << endl;
    return 0;
}

Flip the inner loop forward and you get Coin Change — unlimited supply, the same line of code wearing the other convention. That symmetry is the family tree of knapsack problems in one picture: 0/1 here, unbounded there, and with one more dimension (counts per item) the bounded version. The 2^n brute force you met in Generate Subsets is the fallback when W is astronomically large but n stays tiny.

Deep dive

Why this works

best[c] = the best value achievable with capacity c using the items processed so far. The item loop processes items one at a time; the capacity loop must run backward so every best[c-w] it reads still belongs to the previous row — 'without this item'. Backward is what makes it 0/1; forward would let an item pair with itself, which is exactly unbounded knapsack (coin change).

The cost

O(n × W) time — 20 × 1000 = 20,000 transitions — and O(W) space. The alternative (best per item-subset) would be 2^20 tables; the 1D rolling trick is what collapses the item dimension.

Where it goes wrong

Looping capacity forward reuses items: the first sample (one item, answer 10 instead of 5) is built to catch precisely this.
Trusting a zero-initialized global: this engine does not zero arrays; best[c] = 0 for all c must be explicit.
Swapping w and v on input or in the transition: best[c-w] uses weight, the added term uses value — one swapped symbol inverts the problem silently.

Next step

Forward the loop and it is Coin Change — the unbounded sibling. Backward here is 0/1; per-item counts in between make bounded knapsack. The brute force of Generate Subsets covers tiny n with huge W.

Two things to remember

Backward capacity loop = each item once; forward = unlimited.
Zero the rolling table explicitly; INF/0 sentinels are the DP's load-bearing walls.

🐞 This version fails — open it and try

Capacity loop runs forward — every item pairs with itself

#include <iostream>
using namespace std;

int best[1005];

int main() {
    int n, W;
    cin >> n >> W;
    int w[20], v[20];
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
    for (int c = 0; c <= W; c++) best[c] = 0;
    for (int i = 0; i < n; i++) {
        for (int c = w[i]; c <= W; c++) {   // bug: forward loop reuses items
            if (best[c - w[i]] + v[i] > best[c]) {
                best[c] = best[c - w[i]] + v[i];
            }
        }
    }
    cout << best[W] << endl;
    return 0;
}