Knapsack 0/1 DP (Practice 4063): Notes

Interviewers love knapsack 0/1 dp because it checks whether you can state the invariant before coding. Here is a compact rehearsal note.

Approach

dp[w] = max value with capacity w; iterate items then weights reverse.

def knapsack(W, wt, val):
    dp = [0]*(W+1)
    for w_i, v_i in zip(wt, val):
        for w in range(W, w_i-1, -1):
            dp[w] = max(dp[w], dp[w-w_i] + v_i)
    return dp[W]

Complexity

Linear in the dominant input size for the scan; heap/tree variants add a log factor.

Interview pitfalls

State the invariant out loud, name the complexity, then code. Skipping the invariant is the usual fail mode.

Practicing out loud

Narrate the approach, complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see https://linkjob.ai.