Fractional Loot

easysortingDP

You are planning a heist with access to $$$n$$$ valuable items stored in a warehouse. Each item has:

  • a value $$$v_i$$$ if taken fully, and
  • a weight $$$w_i$$$.

Your backpack can carry at most $$$W$$$ units of weight. Here's the twist: you're allowed to take fractions of any item — you can slice gold bars or siphon oil if needed. Your goal is to maximize the total value of what you carry, without exceeding the weight limit.

Input Format:

The first line contains two integers $$$n$$$ and $$$W$$$ ($$$1 \leq n < 2 \cdot 10^5$$$, $$$1 \leq W \leq 10^9$$$) — the number of items and the maximum weight that can be carried.

Each of the next $$$n$$$ lines contains two integers $$$v_i$$$ and $$$w_i$$$ ($$$1 \leq v_i, w_i \leq 10^5$$$) — the value and weight of the $$$i$$$-th item.

Output Format:

Print a single floating-point number — the maximum total value you can carry. Your answer will be considered correct if $$$ \frac{| \text{correct answer} - \text{your answer} |}{ \text{correct answer} } \leq 10^{-6} $$$

Examples:

Example 1:

Input:

3 10
6 3
4 2
10 5

Output:

20.000000

Example 2:

Input:

3 10
40 20
100 50
30 30

Output:

20.000000

Note:

In TestCase 1

  • There are $$$3$$$ items, and the knapsack can carry at most $$$10$$$ units of weight.
  • The items are:
    • Item 1: Value = $$$6$$$, Weight = $$$3$$$
    • Item 2: Value = $$$4$$$, Weight = $$$2$$$
    • Item 3: Value = $$$10$$$, Weight = $$$5$$$
  • The total weight of all three items is $$$3 + 2 + 5 = 10$$$, which fits exactly into the knapsack.
  • Therefore, we take all three items.
  • Total value collected is $$$6 + 4 + 10 = 20.0$$$.

Code

Loading Editor...