easy

Fractional Knapsack

Items have weights and values, and a knapsack has capacity W. You may take any fraction of an item. Maximise the total value carried.

Constraints
  • 1 ≤ n ≤ 10^5
  • 1 ≤ weight[i], value[i] ≤ 10^6
  • 1 ≤ W ≤ 10^9
Examples
in: weights = [10,20,30], values = [60,100,120], W = 50
out: 240
All of items 1 and 2, then 2/3 of item 3.

Code it yourself

Solve in
Test execution is not yet available for this exercise.Practice journal →Draft saved in this browser.
Hints:
Which approach applies?

Choose an approach to check your pattern recognition, or reveal the discussion when you need help.