Choose Items for a Backpack
Shopify● MediumINTERNOAProblem statement
You have a backpack with a weight limit and a list of items. Return the largest total value you can carry without exceeding the limit.
For this exercise, assume item i has integer weight weights[i] and integer value values[i]. Each item is available once. You may choose no items, and unused capacity is allowed. Items with equal weights or values are still separate items.
The arrays describe the same items in the same order. The backpack limit is capacity.
Function
maxBackpackValue(weights: int[], values: int[], capacity: int) → intExamples
Example 1
weights = [2,3,4]values = [4,5,7]capacity = 5return = 9Take the items of weights 2 and 3. Their total weight is 5 and their total value is 4 + 5 = 9. Taking the weight-4 item alone gives value 7, so 9 is best.
Example 2
weights = [3,5]values = [8,12]capacity = 2return = 0Neither item fits. Choosing no items gives value 0.
Constraints
0 <= weights.length <= 200values.length == weights.length1 <= weights[i] <= 100000 <= values[i] <= 100000 <= capacity <= 10000