Back to Challenges0/1 KnapsackMedium 30 min

0/1 Knapsack

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. You cannot split items (0/1 choice).

Examples

Input: values = [60, 100, 120], weights = [10, 20, 30], W = 50

Output: 220

Take item 2 and item 3 for a weight of 50 and value 220.

Constraints

• 1 <= values.length <= 1000
• 1 <= W <= 1000
• weights[i] <= W

Complexity Analysis

Time

O(n * W)

iterating items and weight capacity.

Space

O(W)

using 1D space optimized array.

Test Cases

#1 Standard Knapsack

Input: [60, 100, 120], [10, 20, 30], 50

Expected: 220

#2 Lightweight items

Input: [10, 20, 30], [1, 1, 1], 2

Expected: 50

JavaScript

Output

Click "Run Code" to see output here...