Coding · Dynamic programming
0/1 Knapsack
- Appears on company lists
- Medium
- 1 source
Company-tagged lists or prep guides name it; no candidate write-up was found.
Solve it in the playground, with tests
You have items with given weights and values and a bag that can carry a total weight of at most capacity. Each item can be taken once or left behind. Return the largest total value you can carry. For weights [1,3,4,5], values [1,4,5,7] and capacity 7 the answer is 9, from the items of weight 3 and 4. There are up to 200 items, the capacity goes up to 10,000, and weights and values are non-negative integers. This is a guide level question: a prep guide gives it as its dynamic programming example for Zerodha, and no candidate report of it was found.
Restated in our own words, not a quote from Zerodha or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would begin with the source: one prep guide names 0/1 knapsack as its dynamic programming example for Zerodha, and I found no candidate report of it, so this is guide level practice on a standard problem. Then I would clarify. May an item be split? (No, that is the fractional version, which greedy solves.) Can an item be used more than once? (No, that is the unbounded version.) Are weights integers, and can one be zero? Do I return only the best value or also the chosen items? How big is the capacity, since the table size depends on it?
Assumptions I would state: whole items only, each once, non-negative integer weights and values, and only the best value is returned.
Brute force
Say the obvious answer and why it is too slow.
Each item is either in the bag or out, so there are 2n subsets. Enumerate them, add up the weight and value of each, and keep the best one that fits. With 200 items that is far beyond any machine. A recursive version, solve(i, room) = the better of skipping item i or taking it, has the same exponential cost.
The waste is visible in the recursion: the pair (i, room) is reached by many different earlier choices, and every visit redoes the same subproblem. There are only n times (capacity + 1) distinct pairs, so remembering their answers collapses the exponential tree into a table.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(2^n × n)
- Time
- O(n × capacity)
- Space
- O(capacity)
The pattern is a knapsack table indexed by capacity. Let best[i][room] be the largest value achievable using only the first i items with a weight limit of room. Item i is either skipped, which keeps best[i-1][room], or taken, which adds its value to the best that fits in the remaining room: best[i-1][room - weight] + value, allowed only when the weight is at most room. Take the larger. The answer is best[n][capacity].
Row i reads only row i-1, so a single array is enough. The detail that makes it work: update the cells for each item from the high room down to the low room. When cell room is updated, the cell room - weight lies below it and has not been touched yet for this item, so it still holds the previous row's value. Going upward would read cells that already include this item and could take the same item again, which silently solves the unbounded problem.
Why is it correct? By induction over the items, the array holds the best value for every limit using the items seen so far. The array starts as all zeros, meaning "weight at most room", so a cell never needs an impossible marker. Each item adds exactly the two options of skip or take, and nothing else. The cost is n times capacity, which is polynomial in the capacity's value but not in the number of bits needed to write it.
Out loud: "For each item I go through the capacities from big to small and ask whether taking it beats leaving it."
Walk it through
A dry run on the example, step by step.
| Item | Weight | Value | dp[0] to dp[7] |
|---|---|---|---|
| start | - | - | 0 0 0 0 0 0 0 0 |
| 1 | 1 | 1 | 0 1 1 1 1 1 1 1 |
| 2 | 3 | 4 | 0 1 1 4 5 5 5 5 |
| 3 | 4 | 5 | 0 1 1 4 5 6 6 9 |
| 4 | 5 | 7 | 0 1 1 4 5 7 8 9 |
Take weights [1,3,4,5], values [1,4,5,7] and capacity 7. The array holds the best value for each room from 0 to 7, starting all zeros. Item 1 (weight 1, value 1) lifts every cell from room 1 upward to 1. Item 2 (weight 3, value 4) turns room 3 into 4 and rooms 4 to 7 into 5, since room 4 can hold item 1 plus item 2.
Item 3 (weight 4, value 5) updates room 7 to dp[3] + 5 = 4 + 5 = 9, the weights 3 and 4 together. It also lifts rooms 5 and 6 to 6. Item 4 (weight 5, value 7) improves room 5 to 7 and room 6 to 8 but not room 7, since dp[2] + 7 = 8 is below 9. The answer is the last cell, 9.
The code
Runnable JavaScript, checked against test cases.
function knapsack(weights, values, capacity) {
const best = new Array(capacity + 1).fill(0);
for (let item = 0; item < weights.length; item++) {
for (let room = capacity; room >= weights[item]; room--) {
best[room] = Math.max(best[room], best[room - weights[item]] + values[item]);
}
}
return best[capacity];
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Capacity 0: only items of weight 0 can be taken, and the array has a single cell.
- No items: the array stays at zeros and the answer is 0.
- An item heavier than the capacity: its loop starts below its weight and never runs, so the item is ignored.
- A zero-weight item: each cell reads its own old value before writing, so the item is counted once, not repeatedly.
- An item that exactly fills the bag: taking it reads cell 0, the value of the zero-weight items alone, and adds its own value.
- All items fit: the answer is the sum of all values.
- Values of zero: they never improve a cell, which is harmless.
Follow-ups to expect
Where the interviewer pushes next.
- How would you recover which items were chosen, and what extra information would you store?
- How would you solve it when the capacity is huge but the values are small, by swapping the roles of weight and value in the table?
- How does the code change for the unbounded knapsack, where every item can be taken any number of times?
- How is the equal-sum partition problem a 0/1 knapsack, and which boolean table does it need?
- Why does a greedy choice by value per unit weight fail here but succeed when items can be split?
Where candidates slip
The mistakes this problem punishes.
The classic slip is looping the capacity upward in the one-dimensional version. That lets an item be taken again within the same pass and returns the unbounded answer.
- Choosing items greedily by value per unit weight. On this example it takes weight 5 first, then weight 1, and reaches 8 instead of 9.
- Using a table sized capacity instead of capacity + 1, which loses the last cell.
- Mixing the two meanings of the table: starting from zeros means "weight at most room" and the last cell is the answer, while starting from minus infinity except cell 0 means "weight exactly room" and the answer is the largest cell.
- Looping the room down to 1 instead of down to the item's weight, which reads a negative index.
- Mixing up the weight and value arrays.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.