Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

    • Fractional knapsack

    Given n items with their weights and values, you would like to put those items in a knapsack of capacity W to get the maximum total value in your knapsack. You’re allowed to take some fraction (part) of an item, in which case the price changes proportionally to the fraction you’ve taken.
    What would be the maximum total value of the knapsack?

    Input

    The first line of the input contains two integers n (1 ≤ n ≤ ) the number of items, and W (1 ≤ W ≤ ) the capacity of your knapsack.
    The next n lines contain space-separated pairs of integers (1 ≤ , ≤ ) the weight and the value of each item.

    Output

    The program should print the maximum total value of the knapsack.

    Examples

    Input
    Output
    3 50 10 60 20 100 30 120
    240
    4 60 40 280 10 100 20 120 24 120
    440

    Explanation

    1. 60 + 100 + (2/3)120 = 240
    1. 280 + 100 + (10/20)120 = 440
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue