FunctionRacerProblemsRace

Best Haul With Partial Sacks

EasyGreedyPython, JavaScript, TypeScript, Java, C++

Sack i weighs weights[i] kilograms and is worth values[i] in total. Your cart carries at most limit kilograms. You may load any sack whole, or any fraction of it: loading a fraction f of sack i adds f * weights[i] kilograms and f * values[i] worth.

Return the largest total worth you can load, as a float. The largest worth is unique, so no tie rule is needed. Return 0.0 when weights is empty or limit is 0.

Example 1

weights [10,20,30]
values [60,100,120]
limit 50
returns 240.0

Worth per kilogram is 6, 5 and 4. Load the first two sacks whole (30 kg, worth 160) and 20 of the 30 kg of the third, worth 80 more.

Example 2

weights [5,4]
values [10,4]
limit 3
returns 6.0

The first sack is worth 2 per kilogram, the second 1; three kilograms of the first sack are worth 6.0.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Greedy problems