Back to Problems

0/1 Knapsack

Medium
dynamic-programming

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

Each item can only be selected once (hence 0/1 - either take it or leave it).

You are given two integer arrays:

  • weights[i] is the weight of the i-th item
  • values[i] is the value of the i-th item
  • W is the maximum weight capacity

Return the maximum value that can be achieved.

Recurrence Relation:

  • dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i]] + values[i]) if w >= weights[i]
  • dp[i][w] = dp[i-1][w] if w < weights[i]

This is the fundamental bounded knapsack problem and a cornerstone of DP.

Example 1

Input: weights = [1,2,3], values = [6,10,12], W = 5
Output: 22
Explanation: Take items with weights 2 and 3 for total value 10 + 12 = 22.

Example 2

Input: weights = [1,1,1], values = [10,20,30], W = 2
Output: 50
Explanation: Take items with values 20 and 30 for total value 50.

Example 3

Input: weights = [5], values = [10], W = 4
Output: 0
Explanation: The single item is too heavy for the knapsack.

Constraints

  • •1 <= n <= 100
  • •1 <= weights[i], values[i] <= 1000
  • •1 <= W <= 1000
Show Hints (4)
Hint 1: For each item, you have two choices: include it or exclude it.
Hint 2: dp[i][w] represents the maximum value using items 0..i with capacity w.
Hint 3: If you include item i, you add its value but reduce capacity by its weight.
Hint 4: If you exclude item i, you keep the same capacity.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?