Coding interview problems › Dynamic Programming

🪙 Dynamic Programming Medium

0/1 Knapsack

0/1 Knapsack explained: the take-or-skip DP table, row-by-row filling, the 1D space trick and why greedy-by-ratio fails, with tested Python and a live visual.

Also searched as: 0/1 knapsack dp table · knapsack problem dynamic programming · 0 1 knapsack example

🎒

Try it live Free

0/1 Knapsack (DP)

Watch the dp table fill row by row, each cell one take-or-skip decision built from the row above, then trace back which items made the bag and see greedy-by-ratio strand space and lose.

Also useful: 2D DP Table: LCS & Edit Distance

Open the playground →

The problem

You have n items, each with a weight and a value, and a bag that holds at most W weight. Each item is either taken whole or left behind (no fractions, no repeats). Return the maximum total value that fits.

Inputweights = [1, 3, 4, 5], values = [1, 4, 5, 7], W = 7
Output9

Take the items of weight 3 and 4.

Inputweights = [10, 20, 30], values = [60, 100, 120], W = 50
Output220

Greedy by value per kg takes 10 + 20 for 160; the best is 20 + 30.

The key insight

Build a table where dp[i][w] is the best value using only the first i items with capacity w. For item i there are two choices: skip it (dp[i-1][w]) or take it if it fits (dp[i-1][w - wt] + val). Each cell looks only at the row above, so you can even keep a single row and sweep capacities from high to low.

Brute force first: Trying all 2n subsets of items is correct but exponential.

Step-by-step approach

  1. Create a 1D array dp of size W + 1 filled with 0 (no items yet).
  2. For each item (wt, val), loop capacity w from W down to wt.
  3. Set dp[w] = max(dp[w], dp[w - wt] + val): skip versus take.
  4. Going downward guarantees dp[w - wt] still holds the previous row, so each item is used at most once.
  5. Return dp[W].

Python solution

PYTHON 3tested
def knapsack(weights, values, W):
    dp = [0] * (W + 1)               # dp[w] = best value with capacity w
    for wt, val in zip(weights, values):
        for w in range(W, wt - 1, -1):   # downward: each item once
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]

Complexity

TimeO(n · W)
SpaceO(W)

There are n × W take-or-skip decisions, each O(1). Keeping only one row cuts space from O(n · W) to O(W). This is pseudo-polynomial: it depends on the numeric value of W.

Common mistakes

Frequently asked questions

What is the time and space complexity of 0/1 Knapsack?

O(n × W) time. The full table uses O(n × W) space; the single-row version uses O(W).

Why do we iterate capacity backwards in the 1D knapsack?

dp[w - wt] must still be the value from before this item was considered. Going from high w to low w means we read cells that have not been updated for the current item yet.

How do I find which items were chosen?

Keep the 2D table. Starting at dp[n][W], if dp[i][w] differs from dp[i-1][w], item i was taken, so subtract its weight; then move to row i-1.

What is the difference between 0/1 and fractional knapsack?

Fractional knapsack lets you take part of an item, and greedy by value per weight is optimal there. In 0/1 knapsack items are indivisible, so you need DP.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Dynamic Programming Coin Change (DP) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.