0/1 Knapsack Practice Problem

Let's apply the 0/1 knapsack pattern with a practical example.

Given n items where item i has weight weights[i] and value values[i], find the maximum total value achievable without exceeding capacity max_weight. Each item can be selected at most once.

Input

• weights: an array of integers that denote the weights of objects
• values: an array of integers that denote the values of objects
• max_weight: the maximum weight capacity of the knapsack

Output

the maximum value in the knapsack

Examples

Example 1:

Input:

weights = [3, 4, 7]
values = [4, 5, 8]
max_weight = 7

Output: 9

Explanation:

We have a knapsack of max limit 7 with 3 objects of weight-value pairs of [3,4], [4,5], [7,8], then the maximal value we can achieve is using the first 2 objects to obtain value 4 + 5 = 9.

The other possibilities would all be only 1 object in our knapsack, which would only yield values 4, 5, and 9.

Try it yourself