Fractional Knapsack
Medium · Greedy · about 15 minutes
Asked at Amazon, Microsoft, Google.
You have items with weights[i] and values[i] and a bag of capacity capacity. You may take any fraction of an item (taking half of it gives half its value). Return the maximum total value you can carry (answers within 1e-5 are accepted).