Pack Grain Sacks by Value per Kilo
Implement maxPackedValue
A trader has sacks of grain. Sack i is worth values[i] in total and weighs weights[i] kilos, and the truck can carry capacity kilos. Unlike an all-or-nothing load, any sack may be split: taking a fraction of a sack gives the same fraction of its value and weight. Find the maximum total value that fits, rounded down to a whole number.
Because sacks can be split, the best use of every kilo is the grain with the highest value per kilo. Ranking the sacks by that ratio and filling greedily — whole sacks first, then a fraction of the first one that doesn't fit — is optimal.
Example 1:
Input: values = [40,30,91,20], weights = [8,5,30,10], capacity = 35
Output: 136
Example 2:
Input: values = [50], weights = [20], capacity = 10
Output: 25
Example 3:
Input: values = [10,10,10], weights = [5,5,5], capacity = 12
Output: 24
+ 9 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ values.length ≤ 12, and weights.length equals values.length - ●
1 ≤ values[i] ≤ 100 and 1 ≤ weights[i] ≤ 50; sack i is worth values[i] in total and weighs weights[i] kilos - ●
1 ≤ capacity ≤ 300 kilos - ●
Any sack may be split: taking a fraction f of sack i adds f × values[i] in value and f × weights[i] in weight - ●
Return the maximum total value, rounded down to a whole number
values =
weights =
capacity =