0/1 Knapsack: Best Value Within a Weight Limit
Problem statement
You have n items. Item i weighs weights[i] and is worth values[i]. Your bag can carry a total weight of at most capacity.
Choose a set of items whose total weight is at most capacity and whose total value is as large as possible. Each item can be taken at most once, and items cannot be split. Return the largest total value (0 if nothing fits).
Function
maxKnapsackValue(weights: int[], values: int[], capacity: int) → intExamples
Example 1
weights = [3,4,5]values = [30,50,60]capacity = 8return = 90The weights 3 and 5 fill the capacity of 8 exactly and are worth 30 + 60 = 90. Other choices are worth less: 3 and 4 give 80, and 4 alone or 5 alone give 50 or 60. All three items weigh 12, which is too much.
Example 2
weights = [2,9]values = [7,7]capacity = 0return = 0With capacity 0 nothing fits, so the best value is 0.
Example 3
weights = [5]values = [10]capacity = 4return = 0The only item weighs 5, more than the capacity 4, so nothing can be taken.
Constraints
1 <= weights.length <= 100andvalues.length == weights.length1 <= weights[i] <= 10000 <= values[i] <= 10^40 <= capacity <= 10^4