Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
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 be used at most once (0/1 knapsack).
Input:
- An array of integers
weightswhereweights[i]is the weight of item i - An array of integers
valueswherevalues[i]is the value of item i - An integer
capacityrepresenting the knapsack capacity
Output:
- Maximum value that can be obtained
Constraints:
- 1 ≤ n ≤ 1000
- 1 ≤ weights[i] ≤ 1000
- 1 ≤ values[i] ≤ 1000
- 1 ≤ capacity ≤ 1000
Examples:
Example 1:
Input: weights = [1, 3, 4, 5], values = [1, 4, 5, 7], capacity = 7
Output: 9
Explanation: Take items with weights 3 and 4 (values 4 and 5) for total value 9
Example 2:
Input: weights = [1, 2, 3], values = [6, 10, 12], capacity = 5
Output: 22
Explanation: Take all items (total weight = 6 > 5, so take items 1,2 with value 16... actually take items 2,3 with weight 5 and value 22)
Solutions
Approach 1: 2D Dynamic Programming
Algorithm:
- Create 2D DP table where dp[i][w] = max value using first i items with capacity w
- For each item, decide whether to include it or not
- dp[i][w] = max(exclude item i, include item i if weight allows)
Python:
def knapsack_2d(weights, values, capacity):
"""
2D DP solution for 0/1 knapsack
Time: O(n * W) where n = number of items, W = capacity
Space: O(n * W) for DP table
"""
n = len(weights)
# dp[i][w] = max value using first i items with capacity w
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
# Fill DP table
for i in range(1, n + 1):
for w in range(capacity + 1):
# Option 1: Don't include current item
dp[i][w] = dp[i-1][w]
# Option 2: Include current item (if it fits)
if weights[i-1] <= w:
include_value = values[i-1] + dp[i-1][w - weights[i-1]]
dp[i][w] = max(dp[i][w], include_value)
return dp[n][capacity]
def knapsack_2d_with_items(weights, values, capacity):
"""
2D DP with item tracking
Time: O(n * W)
Space: O(n * W)
"""
n = len(weights)
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
# Fill DP table
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i-1][w]
if weights[i-1] <= w:
include_value = values[i-1] + dp[i-1][w - weights[i-1]]
dp[i][w] = max(dp[i][w], include_value)
# Backtrack to find items
selected_items = []
i, w = n, capacity
while i > 0 and w > 0:
if dp[i][w] != dp[i-1][w]:
selected_items.append(i-1) # 0-based index
w -= weights[i-1]
i -= 1
return dp[n][capacity], selected_items[::-1]
# Example usage
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack_2d(weights, values, capacity)) # Output: 9
Java:
class Knapsack {
/**
* 2D DP solution for 0/1 knapsack
* Time: O(n * W)
* Space: O(n * W)
*/
public int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
// dp[i][w] = max value using first i items with capacity w
int[][] dp = new int[n + 1][capacity + 1];
// Fill DP table
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
// Option 1: Don't include current item
dp[i][w] = dp[i - 1][w];
// Option 2: Include current item (if it fits)
if (weights[i - 1] <= w) {
int includeValue = values[i - 1] + dp[i - 1][w - weights[i - 1]];
dp[i][w] = Math.max(dp[i][w], includeValue);
}
}
}
return dp[n][capacity];
}
}
Approach 2: Space Optimized DP (1D)
Since we only need the previous row, optimize space to O(W).
Python:
def knapsack_optimized(weights, values, capacity):
"""
Space-optimized DP solution
Time: O(n * W)
Space: O(W)
"""
n = len(weights)
# dp[w] = max value with capacity w
dp = [0] * (capacity + 1)
# Process each item
for i in range(n):
# Traverse backwards to avoid using updated values
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
def knapsack_optimized_verbose(weights, values, capacity):
"""
Verbose space-optimized version
Time: O(n * W)
Space: O(W)
"""
dp = [0] * (capacity + 1)
for i, (weight, value) in enumerate(zip(weights, values)):
print(f"Processing item {i}: weight={weight}, value={value}")
# Must iterate backwards to avoid overwriting values we still need
for w in range(capacity, weight - 1, -1):
old_value = dp[w]
new_value = dp[w - weight] + value
dp[w] = max(old_value, new_value)
if dp[w] != old_value:
print(f" Updated dp[{w}]: {old_value} -> {dp[w]}")
return dp[capacity]
# Example usage
print(knapsack_optimized([1, 3, 4, 5], [1, 4, 5, 7], 7)) # Output: 9
Java:
class Solution {
/**
* Space-optimized DP solution
* Time: O(n * W)
* Space: O(W)
*/
public int knapsack(int[] weights, int[] values, int capacity) {
int[] dp = new int[capacity + 1];
// Process each item
for (int i = 0; i < weights.length; i++) {
// Traverse backwards to avoid using updated values
for (int w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
}
Key Insights
- Choice at Each Step: For each item, choose to include it or exclude it
- Optimal Substructure: Optimal solution contains optimal solutions to subproblems
- State Definition: dp[i][w] represents max value using first i items with capacity w
- Space Optimization: Only need previous row, can reduce to 1D array
- Backward Iteration: In 1D version, iterate backwards to avoid overwriting needed values
Test Cases
def test_knapsack():
test_cases = [
([1, 3, 4, 5], [1, 4, 5, 7], 7, 9),
([1, 2, 3], [6, 10, 12], 5, 22),
([2, 1, 3], [1, 4, 7], 5, 11),
([1], [1], 1, 1),
([2], [1], 1, 0)
]
for weights, values, capacity, expected in test_cases:
result = knapsack_optimized(weights, values, capacity)
assert result == expected
print(f"weights={weights}, values={values}, capacity={capacity} -> {result} ✓")
test_knapsack()