1. Capacity table
dp[cap] is best value for that capacity.
Array(capacity + 1).fill(0)Typorithm · medium
0/1 Knapsack
▷ Interactive algorithm labzero-one-knapsack-dpdynamic-programmingcapacityoptimization
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn 0/1 Knapsack
Dynamic Programming
0/1 Knapsack chooses the best value under a capacity when each item can be taken once.
The state is best value for a capacity.
Each item updates possible capacities.
Reverse capacity iteration keeps the item single-use.
Preparing algorithm lab…
01
State: best value at capacity.
02
Choice: skip item or take item.
03
Reverse loop enforces 0/1 usage.
04
Time O(n*capacity).
function knapsack(weights, values, capacity) {
const dp = Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let cap = capacity; cap >= weights[i]; cap--) {
dp[cap] = Math.max(dp[cap], dp[cap - weights[i]] + values[i]);
}
}
return dp[capacity];
}Read the implementation
Connect each part of the code to the concept before you type.
2. Process items
Each item can be used at most once.
for (let i = 0; i < weights.length; i++)3. Reverse capacity
Reverse order prevents reusing the same item twice.
for (let cap = capacity; cap >= weights[i]; cap--)4. Take or skip
Compare skipping item with taking it.
dp[cap] = Math.max(dp[cap], dp[cap - weights[i]] + values[i])A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.