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, 4] values = [3, 4, 5] quantities = [3, 2, 1] capacity = 10
Output
14
Explanation
Select item 0 three times (weight 6, value 9) and item 1 once (weight 3, value 4), plus item 2 once (weight 4, value 5). But total weight would be 13 > 10.
Optimal: Select item 0 twice (weight 4, value 6) and item 1 twice (weight 6, value 8). Total weight = 10, total value = 14.