You have a knapsack with a weight capacity W and n items, each with a weight and a value. You can either take an item or leave it (no fractions). Find the maximum total value you can carry without exceeding the weight capacity.
For example, given W = 7, weights = [1, 3, 4, 5], values = [1, 4, 5, 7], the maximum value is 9 (items with weight 3 and 4, values 4 and 5... actually items with weight 4 and 3 giving values 5 and 4 = 9).
Explain your approach to solving this problem and state the time and space complexity.
How to approach it
- Hint 1
For each item, you have two choices: include it or exclude it. Think about how to build up from smaller subproblems.
- Hint 2
Define dp[i][w] as the maximum value using the first i items with capacity w. For each item, decide whether including it improves the value.
- Hint 3
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) if weight[i] <= w, otherwise dp[i][w] = dp[i-1][w].
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.