Sign in
Skip to solution
mediumDSA

How do you solve the 0/1 knapsack problem?

1.1k views
01

Understand the problem

Explain 0/1 knapsack DP.

dpknapsack
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Use DP where dp[w] is the best value for capacity w. For each item, iterate capacities downward (so each item is used once), taking max(dp[w], dp[w - weight] + value). O(n × capacity) time, O(capacity) space.

Solution ready — 2 min read

Classified // press E to declassify

04

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)
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 31 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track