Problem:

Fractional Knapsack Problem

You have $N$ items that you want to put them into a knapsack of capacity $W$. Item $i$ ($1 \le i \le N$) has weight $w_i$ and value $v_i$ for the weight.

When you put some items into the knapsack, the following conditions must be satisfied:

  
The total value of the items is as large as possible.

  
The total weight of the selected items is at most $W$.

  
You can break some items if you want. If you put $w'$($0 \le w' \le w_i$) of item $i$, its value becomes $\displaystyle v_i \times \frac{w'}{w_i}.$

Find the maximum total value of items in the knapsack.

Input

$N$ $W$
$v_1$ $w_1$
$v_2$ $w_2$
:
$v_N$ $w_N$

The first line consists of the integers $N$ and $W$. In the following $N$ lines, the value and weight of the $i$-th item are given.

Output

Print the maximum total value of the items in a line. The output must not contain an error greater than $10^{-6}$.

Constraints

  
$1 \le N \le 10^5$

  
$1 \le W \le 10^9$

  
$1 \le v_i \le 10^9 (1 \le i \le N)$

  
$1 \le w_i \le 10^9 (1 \le i \le N)$

Sample Input 1

3 50
60 10
100 20
120 30

Sample Output 1

240

When you put 10 of item $1$, 20 of item $2$ and 20 of item $3$, the total value is maximized.

Sample Input 2

3 50
60 13
100 23
120 33

Sample Output 2

210.90909091

When you put 13 of item $1$, 23 of item $2$ and 14 of item $3$, the total value is maximized. Note some outputs can be a real number.

Sample Input 3

1 100
100000 100000

Sample Output 3

100



Sample input:
3 50
60 10
100 20
120 30


Sample output:
240

Submission status: Accepted

Solution code:

class Item:
	def __init__(self,v,w):
		self.v=v
		self.w=w
		self.r=v/w
	def __str__(self):
		s='v='+str(self.v)
		s+=',w='+str(self.w)
		s+=',r='+str(self.r)
		return s

n,w=map(int,input().split())
items=[]
for i in range(n):
	vi,wi=map(int,input().split())
	items.append(Item(vi,wi))
	
items.sort(key=lambda x:x.r,reverse=True)

total=0
remain = w
for i in range(n):
	v = items[i].v
	w = items[i].w
	r = items[i].r
	if w <= remain:
		total += v
		remain -= w
	else:
		total += r * remain
		break
			
print(total)

Submission status: Accepted

Solution code:

class Item:
	def __init__(self,v,w):
		self.v=v
		self.w=w
		self.r=v/w

n,w=map(int,input().split())
items=[]
for i in range(n):
	vi,wi=map(int,input().split())
	items.append(Item(vi,wi))
	
items.sort(key=lambda x:x.r,reverse=True)

total=0
remain = w
for i in range(n):
	vi = items[i].v
	wi = items[i].w
	ri = items[i].r
	if wi <= remain:
		total += vi
		remain -= wi
	else:
		total += ri * remain
		break
			
print(total)

Submission status: Accepted

Solution code:
n, w = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
lst.sort(key=lambda x:x[0] / x[1], reverse=True)
rest = w
ans = 0
for val, wei in lst:
  if rest >= wei:
    ans += val
    rest -= wei
  else:
    ans += val / wei * rest
    break
print(ans)

Submission status: Accepted

Solution code:
n,w = map(int,input().split(" "))
pack = []

for _ in range(n):
    x,y = map(int,input().split(" "))
    pack.append([x/y,x,y])

pack.sort()
pp = pack[::-1]

sum = 0
for ele in pp:
    if w-ele[2] > 0:
        sum += ele[1]
        w = w - ele[2]
    else:
        sum += ele[0]*w
        break

print(sum)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/15/ALDS1_15_B

import heapq
n, w = [int(i) for i in input().split()]
res = 0
pq = []

for _ in range(n):
    _v, _w = [int(i) for i in input().split()]
    e = _v / _w
    heapq.heappush(pq, (-e, _v, _w))


while w > 0 and pq:
    e, value, weight = heapq.heappop(pq)
    if w >= weight:
        res += value
        w -= weight
    else:
        res += -e * w
        w = 0
print(res)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
R = []
for i in range(N):
    v, w = map(int, input().split())
    R.append((v/w, v, w))
R.sort(reverse=1)
ans = 0
for _, v, w in R:
    c = min(w, W)
    W -= c
    ans += c * v / w
print(ans)

Submission status: Accepted

Solution code:
readline = open(0).readline

N, W = map(int, readline().split())

R = []

for i in range(N):
    v, w = map(int, readline().split())
    R.append((v / w, v, w))

R.sort(reverse = 1)
ans = 0

for _, v, w, in R:
    c = min(w, W)
    W -= c
    ans += c * v / w

open(1, 'w').write("%.010f\n" % ans)

Submission status: Accepted

Solution code:
from collections import namedtuple
I = namedtuple("I", "k v w")

n, w = map(int, input().split())
s = []

for i in range(n):
    vi, wi = map(int, input().split())
    s.append(I(vi / wi, vi, wi))
s.sort()

ans = 0
while w > 0 and s != []:
    item = s.pop()
    if w < item.w:
        a, b = item.v * w, item.w
        if a % b == 0:
            ans += a // b
        else:
            ans += a / b
    else:
        ans += item.v
    w -= item.w

print(ans)

Submission status: Accepted

Solution code:
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, W = LI()
    vw = [LI() for _ in range(N)]

    vw.sort(key=lambda x: x[0]/x[1], reverse=True)
    ans = 0
    i = 0
    while i < N and W - vw[i][1] > 0:
        ans += vw[i][0]
        W -= vw[i][1]
        i += 1

    if i < N:
        ans += vw[i][0] * W / vw[i][1]

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	fractional_knapsack
# CreatedDate:  2020-06-08 21:46:16 +0900
# LastModified: 2020-06-08 21:53:14 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd


def main():
    N,W = map(int,input().split())
    p = []
    for _ in range(N):
        v,w = map(int,input().split())
        p.append([v/w,v,w])
#    print(p)
    p.sort(reverse=True)
    index=0
    profit=0
    while W>0 and index<N:
        if W>=p[index][2]:
            profit+=p[index][1]
            W-=p[index][2]
        else:
            profit+=p[index][1]*W/p[index][2]
            W-=W
        index+=1
    print(profit)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N,W = map(int,input().split())
    vw = [list(map(int,input().split())) for _ in range(N)]

    for i in range(N):
        vw[i].append(vw[i][0]/vw[i][1])

    vw.sort(reverse = True,key = lambda x:x[2])

    val,wei = 0,0
    for i in range(N):
        if wei + vw[i][1] <= W:
            val += vw[i][0]
            wei += vw[i][1]
        elif wei < W:
            val += vw[i][0]*(W-wei)/vw[i][1]
            wei = W
        else:
            break
    print(val)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

def Main():
    N, capacity = map(int, input().split())
    w_list = list()

    for _ in range(N):
        v, w = map(int, input().split())
        heapq.heappush(w_list, [-1*float(v/w), v, w] )

    total_value = 0

    while len(w_list) != 0:
        item = heapq.heappop(w_list)
        value_per_weight = -1*item[0]
        value = item[1]
        weight = item[2]
        
        if capacity >= weight:
            capacity -= weight
            total_value += value
        else:
            total_value += capacity * value_per_weight
            break
        
    print(total_value)

Main()

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
V = [None]*N
ans = 0
for i in range(N):
    v, w = map(int, input().split())
    V[i] = [v/w, w]
V.sort(reverse=True)
for v, w in V:
    if W > w:
        W -= w
        ans += v*w
    else:
        ans += v*W
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
p=[]
n,w=map(int,input().split())
for i in range(n):
	a,b=map(int,input().split())
	p.append([a/b,a,b])
p.sort(key=lambda x:-x[0])
ans=0
i=0
while w>0 and i<n:
	if w>=p[i][2]:
		ans+=p[i][1]
	else:
		ans+=p[i][1]*(w/p[i][2])
		break
	w-=p[i][2]
	i+=1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

n,wmax=map(int, input().split( ))
U=[]
for _ in range(n):
    v,w =map(int,input().split( ))
    u = v/w
    U.append([-u,v,w])
U.sort()

remains = wmax
i=0
ans = 0
while True:
    try:
        if remains > U[i][2]:
            remains-=U[i][2]
            ans+=U[i][1]
            i+=1
        else:
            ans += U[i][1]*remains/U[i][2]
            break
    except:
        break
print(ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N, W = map(lambda x: int(x), input().split())
    items = [[0, 0] for _ in range(N)]
    for i in range(N):
        items[i] = list(map(lambda x: int(x), input().split()))

    items = sorted(items, key=lambda x: - x[0] / x[1])

    total_value = 0.0
    total_weight = 0.0
    for (v, w) in items:
        if total_weight + w <= W:
            total_weight += w
            total_value += v
            if W == total_weight:
                break
        else:
            rest_weight = W - total_weight
            total_value += (v / w) * rest_weight
            break

    print(f"{total_value:.6f}")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Greedy algorithms - Fractional Knapsack Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_15_B&lang=jp

"""
N, W = map(int, input().split())
items = []
for _ in range(N):
    v, w = map(int, input().split())
    items.append((v/w, v, w))
items.sort()

ans = 0
while W > 0 and items:
    r, v, w = items.pop()
    if W >= w:
        W -= w
        ans += v
    else:
        ans += v * W / w
        W = 0
print(ans)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
W_calc = W
ans = 0

items = []

for _ in range(N):
    v, w = map(int, input().split())
    density = v / w
    items.append([density, v, w])


items.sort(reverse=True)

for density, v, w in items:
    if w < W_calc:
        W_calc -= w
        ans += v
    else:
        ans += W_calc * density
        break

print(ans)

Submission status: Accepted

Solution code:
N,W = [int(i) for i in input().split()]
VW = [[int(i) for i in input().split()] for _ in range(N)]
sVW = sorted(VW, key = lambda x:x[0]/x[1], reverse = True)
ans = 0
for i in sVW:
    if W < i[1]:
        ans += i[0] * W / i[1]
        break
    else:
        ans += i[0]
        W -= i[1]
print(ans)

Submission status: Accepted

Solution code:
first=list(map(int,input().split()))
n,w=first[0],first[1]
data=[]
for i in range(n):
    a=list(map(int,input().split()))
    vpwi=a[0]/a[1]
    data.append([vpwi,a[0],a[1]])
data.sort(reverse=True)

wtot=0
vtot=0
i=0
for i in range(n):
    if wtot+data[i][2]<=w:
        wtot+=data[i][2]
        vtot+=data[i][1]
    else:
        vtot+=data[i][0]*(w-wtot)
        break

print(vtot)

Submission status: Accepted

Solution code:
n , w = map(int, input().split())
val_w = []
for i in range(n):
    a , b = map(int, input().split())
    val_w += [(-a/b, b)]
val_w.sort()
Sum = 0
i = 0
while w and i <= n-1:
    wei = min(w, val_w[i][1])
    Sum += (-val_w[i][0])*wei
    w -= wei
    i += 1
print(Sum)

Submission status: Accepted

Solution code:
import sys

n, W = map(int, sys.stdin.readline().split())

val = []
for i in range(n):
    val.append(list(map(int, sys.stdin.readline().split())))

total=0
for vv in sorted(val, key=lambda x:x[0]/x[1], reverse=True):
    if W>=vv[1]: #   50 > 10
        W -= vv[1]
        total += vv[0]
    else:
        total += W*vv[0]/vv[1]
        break

print(total)

Submission status: Accepted

Solution code:
readline = open(0).readline
N, W = map(int, readline().split())
R = []
for i in range(N):
    v, w = map(int, readline().split())
    R.append((v/w, v, w))
R.sort(reverse=1)
ans = 0
for _, v, w in R:
    c = min(w, W)
    W -= c
    ans += c * v / w
open(1, 'w').write("%.010f\n" % ans)