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 & Output
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
Example
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.