Loading...
Loading...
You are given two lists of numbers values and weights of the same length, and a number capacity. Item i has value values[i] and weight weights[i].
You may take any part of an item: taking a fraction f of item i (where 0≤f≤1) adds f * weights[i] to the total weight and f * values[i] to the total value. Each item can be used at most once.
Return the largest total value you can take while the total weight stays at most capacity.
Your answer is accepted if it is within 10−5 of the correct value, either absolutely or relative to the correct value.
Input: values = [60,100,120], weights = [10,20,30], capacity = 50
Output: 240
Explanation: Take items 0 and 1 whole (weight 30, value 160), then 20 of item 2's 30 weight, worth 120 * 20 / 30 = 80.
Input: values = [1.5,2.5], weights = [0.5,2], capacity = 1
Output: 2.125
Explanation: Item 0 is worth 3 per unit of weight and item 1 is worth 1.25. Take all of item 0 (weight 0.5), then 0.5 of item 1's 2 weight, worth 2.5 * 0.5 / 2 = 0.625.
Input: values = [10], weights = [4], capacity = 0
Output: 0
Explanation: With no room, nothing can be taken.
values.length = weights.length ≤105weights[i] ≤104values[i] ≤104capacity ≤109