• 1 ≤ n ≤ 1000
• 1 ≤ W ≤ 1000
• 1 ≤ weights[i], values[i] ≤ 1000
• Each item is taken either zero times or one time; no fractions

You have a bag with a weight limit and a pile of items, each with a weight and a value. Pick a set of items whose total weight fits, and make their total value as large as possible. The "0/1" in the name means each item is all-or-nothing: you take it whole, or not at all.

That last restriction is the whole difficulty. If you were allowed to take fractions of items, this problem would be easy and would not need a table at all — you would sort the items by value-per-kilogram, greedily fill up with the best ratio first, and slice the last item to fit exactly. That works because with fractions there is never any wasted space.

Take W = 10 with three items: (weight 6, value 30), (weight 5, value 24) and (weight 5, value 24).

Ratios: the first item is 5.0 per kilo, the other two are 4.8 per kilo. So the greedy rule grabs the first item, leaving 4 units of space, which nothing else fits into. Total value: 30.

But taking the two lesser items uses all 10 units and yields 48.

The failure is not bad luck, it is structural: taking the best-ratio item can leave behind a gap that nothing fills. With indivisible items, how well things fit together matters as much as how good each one is on its own, and no per-item ranking can see that. Once a greedy order is provably wrong, the only honest option is to compare the futures of both choices. That is where take-or-skip comes in.

I go through the items one at a time, from the last toward the first. Standing at item i with c units of room left in the bag, I have two choices:

I keep the better of the two. The two things I must track are which item I'm on (i) and how much room is left (c) — the bag doesn't care which items are already inside, only how full it is.

f(i, c) = max( f(i-1, c), values[i] + f(i-1, c - weights[i]) if it fits )

Base case: when only the first item is left (i == 0), take it if it fits, else skip it: f(0, c) = values[0] if weights[0] <= c else 0. Unused capacity costs nothing — you are never forced to fill the bag.

Start with plain recursion, straight from the recurrence — nothing else going on:

def knapsack(weights, values, W):
    n = len(weights)

    def f(i, c):
        if i == 0:                                           # only the first item is left
            return values[0] if weights[0] <= c else 0
        best = f(i - 1, c)                                   # skip
        if weights[i] <= c:                                  # take, if it fits
            best = max(best, values[i] + f(i - 1, c - weights[i]))
        return best

    return f(n - 1, W)

This is correct but slow. Each call splits into two — skip and take — so the tree has about 2ⁿ leaves. Yet only n × (W+1) different (i, c) pairs exist inside it, so the same pairs are recomputed again and again. Fix it with a notebook: before computing f(i, c), check whether it is already stored; if so, return it; if not, compute it once and save it. That drops the work to one computation per state, O(N × W):

def knapsack(weights, values, W):
    n = len(weights)
    memo = {}

    def f(i, c):
        if i == 0:
            return values[0] if weights[0] <= c else 0
        if (i, c) in memo: return memo[(i, c)]
        best = f(i - 1, c)
        if weights[i] <= c:
            best = max(best, values[i] + f(i - 1, c - weights[i]))
        memo[(i, c)] = best
        return best

    return f(n - 1, W)

Now drop the recursion and fill a table instead. Let dp[i][c] hold what f(i, c) returned: the best value from items 0 through i within capacity c. Read the recurrence as an assignment — swap each f(...) call for a dp[...] read:

dp[i][c] = max( dp[i-1][c], values[i] + dp[i-1][c - weights[i]] if it fits )

Each row i reads only row i-1, so fill the rows top to bottom (i = 0, 1, 2, ...). The base case copies straight over: the recursion returned values[0] if weights[0] <= c else 0 at i == 0, so that is row 0. The loop then starts at row i = 1, and the answer is dp[n-1][W]:

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n)]

    for c in range(W + 1):                                   # row 0: only the first item
        dp[0][c] = values[0] if weights[0] <= c else 0

    for i in range(1, n):
        for c in range(W + 1):
            dp[i][c] = dp[i - 1][c]                          # skip
            if weights[i] <= c:
                dp[i][c] = max(dp[i][c],
                               values[i] + dp[i - 1][c - weights[i]])

    return dp[n - 1][W]

Row i only ever reads row i-1, so keep one array. The capacity sweep must run downward, because dp[c - weight] must still hold the previous row's value — the world where this item has not been used yet.

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for c in range(W, w - 1, -1):        # downward keeps each item single-use
            dp[c] = max(dp[c], v + dp[c - w])
    return dp[W]

Answer 48, beating the greedy 30 exactly as predicted.

The knapsack skeleton is one of the highest-yield shapes in interviews, and it is almost never introduced as "here is a bag". The signals to watch for:

That last point deserves a warning. O(N × W) is called pseudo-polynomial: it is linear in the value of W, but W is written in only about log W digits, so doubling the number of digits squares the running time. If a problem gives a capacity of a billion, this table is not the intended solution no matter how knapsack-shaped it looks. The constraint bounds are telling you which technique is expected — read them before you choose.

This is the take-or-skip skeleton once more, now with max because we want the best value. Swap the combining operation and it answers different questions: or asks "is it possible", + counts the arrangements. The state and the walk stay the same; only that one operation changes.