Fractional Knapsack
MediumP2Coding
A thief has a bag that holds total weight capacity. Gem i has value values[i] and weight weights[i], and a gem may be broken into any fraction of itself; a fraction f of a gem has weight f * weights[i] and value f * values[i]. Return the maximum total value that fits in the bag, rounded to the nearest integer (a fractional part of exactly .5 rounds up).
Example 1
- Input
- capacity = 50, values = [60,100,120], weights = [10,20,30]
- Output
- 240
- Why
- Take all of the first two gems and two thirds of the third.
Example 2
- Input
- capacity = 10, values = [60], weights = [20]
- Output
- 30
Constraints
- 1 <= n <= 10^5
- 1 <= capacity <= 10^9
- 1 <= values[i], weights[i] <= 10^6
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 12. ⌘Enter runs, ⌘⇧Enter submits.