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.