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

• 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

Examples

Example 1:

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.

Try it yourself

Solution