mediumDSA

How do you solve the 0/1 knapsack problem?

Q: How do you solve the 0/1 knapsack problem?

**Intuition.** Each item is either taken whole or skipped (the "0/1"). Build up the best achievable value for every capacity using one rolling 1-D array dp[w] . The crucial detail: iterate capacities **downward** when adding an item, so each item contributes to a capacity at most once. for each item, sweep capacity high→low: take vs skip items (w,v): (1,1) (3,4) (4,5) (5,7) cap = 7 <rect x="60" y="70" width="44" height="30" rx="5"

1.1k views

Understand the problem

Explain 0/1 knapsack DP.

dpknapsack

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

1-D DP, capacity swept downward

Run Playground

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):    # high -> low = 0/1
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]


# --- demo ---
weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
print(knapsack(weights, values, 7))   # 9  (weights 3 + 4 -> values 4 + 5)

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you find the k closest points to the origin?

How does binary search work and what are its requirements?