You have n item types. For item type i, you know its weight
weights[i], its value values[i], and an available count counts[i] — meaning you can take at most counts[i] copies of that item. Given a knapsack of capacity capacity, find the maximum total value you can pack without exceeding capacity.Input
weights: array of positive integers — weight per item type
values: array of positive integers — value per item type
counts: array of positive integers — max copies allowed per item type
capacity: positive integer — knapsack capacity
Output
The maximum total value achievable.
Examples
Example 1
Inputweights = [1, 2], values = [3, 5], counts = [2, 1], capacity = 4
Output11
ExplanationTake 2 copies of item 0 (weight 2, value 6) plus 1 copy of item 1 (weight 2, value 5). Total weight 4, total value 11.
Example 2
Inputweights = [2], values = [3], counts = [3], capacity = 6
Output9
ExplanationThree copies of the only item; weight 6, value 9.