Bounded Knapsack
Prerequisite: Bounded Knapsack
Given n items where the i-th item has weight weights[i], value values[i], and can be selected at most quantities[i] times, find the maximum total value that fits in a knapsack of capacity capacity.
Input & Output
Input
weights — weights of each item
values — values of each item
quantities — maximum number of times each item can be selected
capacity — maximum weight the knapsack can hold
Output
maximum achievable value
Example
Input
weights = [2, 3] values = [5, 8] quantities = [2, 1] capacity = 5
Output
13
Explanation
Take item 0 once (weight 2, value 5) and item 1 once (weight 3, value 8) for weight 5 and value 13. Item 1 cannot be taken twice because its quantity is 1, and taking item 0 twice instead gives only weight 4 and value 10.
Example
Input
weights = [2, 3, 4] values = [3, 4, 5] quantities = [3, 2, 1] capacity = 10
Output
14
Explanation
Taking item 0 three times (weight 6, value 9), item 1 once (weight 3, value 4), and item 2 once (weight 4, value 5) would need weight 13, over the capacity of 10.
The best that fits is item 0 twice (weight 4, value 6) plus item 1 twice (weight 6, value 8), for weight 10 and value 14.
Constraints
1 <= weights.length == values.length == quantities.length <= 1001 <= weights[i] <= 10001 <= values[i] <= 10001 <= quantities[i] <= 10001 <= capacity <= 10000