Given weights and values of N items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
Note: Unlike 0/1 knapsack, you are allowed to break the item. 
 
Example 1:
Input:
N = 3, W = 50
values[] = {60,100,120}
weight[] = {10,20,30}
Output:
240.00
Explanation:Total maximum value of item
we can have is 240.00 from the given
capacity of sack. 
Example 2:
Input:
N = 2, W = 50
values[] = {60,100}
weight[] = {10,20}
Output:
160.00
Explanation:
Total maximum value of item
we can have is 160.00 from the given
capacity of sack.
 
Your Task :
Complete the function fractionalKnapsack() that receives maximum capacity , array of structure/class and size n and returns a double value representing the maximum value in knapsack.
Note: The details of structure/class is defined in the comments above the given function.
Expected Time Complexity : O(NlogN)
Expected Auxilliary Space: O(1)
Constraints:
1 <= N <= 10^{5}
1 <= W <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Greedy algorithms

Starter code: #User function Template for python3



class Item:

    def __init__(self,val,w):

        self.value = val

        self.weight = w

        

class Solution:    

    #Function to get the maximum total value in the knapsack.

    def fractionalknapsack(self, W,arr,n):

        

        # code here

Solutions:
class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda x: -1 * (x.value / x.weight))
		profit = 0
		for i in range(n):
			v = arr[i].value
			w = arr[i].weight
			if w <= W:
				W -= w
				profit += v
			else:
				profit += W * (v / w)
				W = 0
				break
		return profit


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		fractionalArray = []
		for i in range(n):
			fractionalArray.append([arr[i].value, arr[i].weight, arr[i].value / arr[i].weight])
		fractionalArray = sorted(fractionalArray, key=lambda x: -x[2])
		ans = 0
		while W > 0 and len(fractionalArray) > 0:
			popped = fractionalArray.pop(0)
			if popped[1] > W:
				ans += popped[0] * W / popped[1]
				W = 0
			else:
				W -= popped[1]
				ans += popped[0]
		return round(ans, 2)


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		d = []
		for i in range(0, len(arr)):
			k = (arr[i].value, arr[i].weight, arr[i].value / arr[i].weight)
			d.append(k)
		d.sort(key=lambda x: x[2], reverse=True)
		p = 0
		for i in range(0, len(d)):
			if d[i][1] <= W:
				W -= d[i][1]
				p += d[i][0]
			elif d[i][1] > W:
				p += d[i][0] * (W / d[i][1])
				break
		return p


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, w, arr, n):
		count = 0

		def give(i):
			return i.value / i.weight
		arr.sort(reverse=True, key=give)
		for i in arr:
			ass = min(w, i.weight)
			count += ass * i.value / i.weight
			w -= ass
			if ass == 0:
				return count
		return count


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		items = sorted(arr, key=lambda x: x.weight / x.value)
		result = 0
		for item in items:
			if W <= 0:
				break
			result += min(1, W / item.weight) * item.value
			W -= item.weight
		return result


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		frac = [[items.value / items.weight, items.weight] for items in arr]
		frac.sort(key=lambda x: x[0])
		val = 0
		while W and frac:
			a = frac.pop()
			k = a[0]
			p = a[1]
			if W >= p:
				val += k * p
				W -= p
			else:
				val += k * W
				W = 0
		return val


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, w, arr, n):
		arr.sort(key=lambda x: -1 * (x.value / x.weight))
		value = 0
		for item in arr:
			if w <= item.weight:
				value += item.value * (w / item.weight)
				break
			else:
				value += item.value
				w -= item.weight
		return value


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		total = 0
		remaining_weight = W
		arr.sort(key=lambda x: x.value / x.weight, reverse=True)
		for item in arr:
			if item.weight <= remaining_weight:
				total += item.value
				remaining_weight -= item.weight
			else:
				total += remaining_weight * item.value / item.weight
				break
		return total


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, Items, n):
		arr = []
		total = 0
		s = 0
		for i in range(n):
			x = Items[i].value / Items[i].weight
			arr.append([x, i])
		arr.sort(reverse=True)
		for i in range(n):
			if s + Items[arr[i][1]].weight < W:
				total += Items[arr[i][1]].value
				s += Items[arr[i][1]].weight
			else:
				total += (W - s) * arr[i][0]
				break
		return total


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		li = []
		for i in range(n):
			perUnitVal = arr[i].value / arr[i].weight
			li.append((perUnitVal, arr[i]))
		li.sort(key=lambda x: x[0], reverse=True)
		profit = 0
		for pair in li:
			if pair[1].weight <= W:
				profit += pair[1].value
				W -= pair[1].weight
			else:
				profit += pair[1].value / pair[1].weight * W
				W = 0
				break
		return profit


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda x: x.value / x.weight, reverse=True)
		curWeight = 0
		finalValue = 0.0
		for i in range(n):
			if curWeight + arr[i].weight <= W:
				curWeight += arr[i].weight
				finalValue += arr[i].value
			else:
				remain = W - curWeight
				finalValue += arr[i].value / arr[i].weight * remain
				break
		return finalValue


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		rr = []
		arr.sort(reverse=True, key=lambda x: x.value / x.weight)
		ans = 0
		for ind in range(len(arr)):
			cap = min(W, arr[ind].weight)
			if arr[ind].weight <= W:
				ans += arr[ind].value
				W -= arr[ind].weight
				continue
			rat = arr[ind].value / arr[ind].weight
			ans += rat * cap
			W -= cap
		return ans


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda x: x.value / x.weight, reverse=True)
		profit = 0
		for i in arr:
			if i.weight <= W:
				profit += i.value
				W -= i.weight
			elif i.weight > W:
				profit += i.value / i.weight * W
				W = 0
				break
		return profit


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda x: x.value / x.weight, reverse=True)
		final = 0
		cur = 0
		for i in range(n):
			if cur + arr[i].weight <= W:
				cur += arr[i].weight
				final += arr[i].value
			else:
				rem = W - cur
				final += arr[i].value / arr[i].weight * rem
				break
		return final


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		ans = 0
		vpp = []
		for ob in arr:
			(w, v) = (ob.weight, ob.value)
			vpp.append([v / w, v, w])
		vpp.sort()
		while vpp and W:
			(vp, v, w) = vpp.pop()
			if W >= w:
				W -= w
				ans += v
			else:
				ans += W * vp
				W -= W
		return ans


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		for a in arr:
			a.avg = a.value / a.weight
		arr.sort(key=lambda x: x.avg, reverse=True)
		(final_val, i) = (0, 0)
		while W > 0 and i < n:
			if arr[i].weight < W:
				final_val += arr[i].value
				W -= arr[i].weight
			else:
				final_val += W * arr[i].avg
				W = 0
			i += 1
		return final_val


import heapq

class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):

		class Wrapper:

			def __init__(self, item):
				self.val = item.value / item.weight
				self.w = item.weight

			def __lt__(self, other):
				return self.val > other.val
		h = [Wrapper(a) for a in arr]
		heapq.heapify(h)
		value = 0
		w = 0
		while w < W and h:
			item = heapq.heappop(h)
			tmp = min(item.w, W - w)
			w += tmp
			value += tmp * item.val
		return value


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda x: x.value / x.weight, reverse=True)
		total_value = 0.0
		current_weight = 0
		for i in range(n):
			if current_weight + arr[i].weight <= W:
				current_weight += arr[i].weight
				total_value += arr[i].value
			else:
				remaining_weight = W - current_weight
				fraction = remaining_weight / arr[i].weight
				total_value += fraction * arr[i].value
				break
		return total_value


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda x: x.value / x.weight, reverse=True)
		result = 0
		current_cap = W
		for i in arr:
			if i.weight <= current_cap:
				current_cap -= i.weight
				result += i.value
			else:
				result += i.value * (current_cap / i.weight)
				break
		return result


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, Items, n):
		Items.sort(key=lambda x: x.value / x.weight, reverse=True)
		res = 0
		for i in Items:
			if i.weight <= W:
				res += i.value
				W -= i.weight
			else:
				temp = i.value / i.weight * W
				res += temp
				W = 0
		return res


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda x: x.value / x.weight, reverse=True)
		i = 0
		res = 0
		while W > 0 and i < n and (arr[i].weight <= W):
			W -= arr[i].weight
			res += arr[i].value
			i += 1
		if W > 0 and i < n:
			res += arr[i].value * (W / arr[i].weight)
		return res


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		val = []
		for i in range(n):
			val.append([arr[i].value / arr[i].weight, arr[i].weight, arr[i].value])

		def sort(arr1):
			arr1 = sorted(arr1, key=lambda x: x[0], reverse=True)
			return arr1
		val1 = sort(val)
		pro = 0
		for i in range(n):
			if W >= val1[i][1]:
				W -= val1[i][1]
				pro = pro + val1[i][2]
			else:
				pro = pro + val1[i][2] * W / val1[i][1]
				break
		return pro


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		ratios = []
		for i in range(n):
			ratios.append([i, arr[i].value / arr[i].weight])
		ratios = sorted(ratios, key=lambda x: x[1], reverse=True)
		(capacity, value) = (0, 0)
		for i in range(len(ratios)):
			if capacity + arr[ratios[i][0]].weight < W:
				value += arr[ratios[i][0]].value
				capacity += arr[ratios[i][0]].weight
			else:
				x = W - capacity
				value += x * ratios[i][1]
				break
		return value


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		l = []
		for i in arr:
			l.append((i.value / i.weight, i.value, i.weight))
		l = sorted(l, key=lambda x: x[0], reverse=True)
		cap = 0
		for i in l:
			if i[2] > W:
				val = i[0] * W
				cap += val
				W = 0
				break
			cap += i[1]
			W -= i[2]
		return cap


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):

		def myfunct(ele):
			return ele.value / ele.weight
		arr.sort(reverse=True, key=myfunct)
		ans = 0
		for i in arr:
			if i.weight <= W:
				ans += i.value
				W -= i.weight
			else:
				ans += W * (i.value / i.weight)
				break
		return ans


import math

class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda x: x.weight / x.value, reverse=False)
		p = 0
		for i in arr:
			if i.weight <= W:
				p += i.value
				W -= i.weight
			elif i.weight > W:
				p += W / i.weight * i.value
				W = 0
				break
		return p


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda x: x.value / x.weight, reverse=True)
		curr_weight = 0
		max_value = 0
		for i in range(n):
			if arr[i].weight + curr_weight <= W:
				curr_weight += arr[i].weight
				max_value += arr[i].value
			else:
				left_weight = W - curr_weight
				max_value += arr[i].value * left_weight / arr[i].weight
				break
		return max_value


import heapq

class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		heap = []
		for (i, item) in enumerate(arr):
			heap.append([-item.value / item.weight, i])
		heapq.heapify(heap)
		remaining_capacity = W
		res = 0
		while heap and remaining_capacity > 0:
			(value_per_weight, index) = heapq.heappop(heap)
			value_per_weight *= -1
			if arr[index].weight > remaining_capacity:
				res += value_per_weight * remaining_capacity
				break
			else:
				res += arr[index].value
				remaining_capacity -= arr[index].weight
		return res


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		s = ans = wt = 0
		fact = []
		for i in range(n):
			fact.append([arr[i].value / arr[i].weight, i])
		fact = sorted(fact, reverse=True)
		for i in range(n):
			if wt + arr[fact[i][1]].weight <= W:
				ans += arr[fact[i][1]].value
				wt += arr[fact[i][1]].weight
			else:
				x = W - wt
				ans += fact[i][0] * x
				break
		return ans


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, Items, n):
		Items.sort(key=lambda x: x.value / x.weight, reverse=True)
		value = 0
		for item in Items:
			if item.weight <= W:
				W -= item.weight
				value += item.value
			elif item.weight > W:
				value += item.value * W / item.weight
				W = 0
				break
		return value


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

	def __str__(self):
		return str(self.value)

	def __repr__(self):
		return 'Item value:% s weight:% s' % (self.value, self.weight)

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda item: item.value / item.weight, reverse=True)
		idx = 0
		value = 0.0
		while W > 0 and idx < len(arr):
			if arr[idx].weight <= W:
				value += arr[idx].value
				W -= arr[idx].weight
			else:
				value += W / arr[idx].weight * arr[idx].value
				W -= W


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		vw = []
		for i in range(n):
			v = arr[i].value
			w = arr[i].weight
			vw.append([v / w, v, w])
		vw.sort()
		vw.reverse()
		ans = 0
		for (r, v, w) in vw:
			if W - w >= 0:
				ans += v
				W -= w
			else:
				ans += W / w * v
				break
		return ans


from operator import itemgetter

class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, N):
		values = []
		weight = []
		for i in range(n):
			values.append(arr[i].value)
			weight.append(arr[i].weight)
		valuability = []
		for i in range(len(values)):
			valuability.append([values[i] / weight[i], weight[i]])
		res = sorted(valuability, key=itemgetter(0), reverse=True)
		total = 0
		for i in res:
			if i[1] < W:
				W -= i[1]
				total += i[0] * i[1]
			elif W > 0:
				total += i[0] * W
				W = 0
		return total


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		ans = []
		for i in range(0, n):
			perunit = arr[i].value / arr[i].weight
			ans.append([perunit, arr[i].value, arr[i].weight])
		ans.sort(key=lambda x: x[0], reverse=True)
		total = 0
		for i in range(0, n):
			if ans[i][2] > W:
				total += W * ans[i][0]
				W = 0
			else:
				total += ans[i][1]
				W -= ans[i][2]
		return total


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		curweight = 0
		a = []
		for i in range(n):
			v = [arr[i].value, arr[i].weight]
			a.append(v)
		a.sort(key=lambda x: x[0] / x[1], reverse=True)
		i = 0
		finalvalue = 0
		while curweight < W and i < n:
			if curweight + a[i][1] < W:
				curweight = curweight + a[i][1]
				finalvalue += a[i][0]
			else:
				new = W - curweight
				finalvalue += a[i][0] * new / a[i][1]
				curweight += new
			i += 1
		return finalvalue


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda x: x.value / x.weight, reverse=True)
		(u, tp) = (W, 0)
		dp = [0] * n
		i = 0
		while i < n:
			if arr[i].weight > u:
				break
			dp[i] = 1
			tp += arr[i].value
			u -= arr[i].weight
			i += 1
		if i < n:
			dp[i] = u / arr[i].weight
			tp += dp[i] * arr[i].value
		return tp


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		suml = 0
		weight = 0
		arr = sorted(arr, key=lambda x: x.value / x.weight, reverse=True)
		for x in arr:
			if weight + x.weight <= W:
				suml += x.value
				weight += x.weight
			else:
				suml += (W - weight) / x.weight * x.value
				break
		return suml

	def print_arr(self, arr):
		for x in arr:
			print('[{0} {1}]'.format(x.value, x.weight), end=' ')
		print()


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr = sorted(arr, key=lambda x: x.value / x.weight, reverse=True)
		rem_weight = W
		tot_value = 0
		i = 0
		while rem_weight > 0:
			if i == n:
				return tot_value
			if arr[i].weight < rem_weight:
				rem_weight -= arr[i].weight
				tot_value = tot_value + arr[i].value
				i += 1
			else:
				alpha = arr[i].value / arr[i].weight
				tot_value = tot_value + rem_weight * alpha
				break
		return tot_value


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w
		self.valForMoney = val / weight

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr = [(i.value / i.weight, i) for i in arr]
		arr.sort(key=lambda a: -a[0])
		profits = 0
		for i in arr:
			if i[1].weight <= W:
				(W, profits) = (W - i[1].weight, profits + i[1].value)
			elif W == 0:
				break
			else:
				(W, profits) = (0, profits + W * i[0])
		return profits


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda x: x.weight / x.value)
		curr = W
		i = 0
		rw = 0
		while curr != 0.0 and i < n:
			if arr[i].weight <= curr:
				curr -= arr[i].weight
				rw += arr[i].value
				i += 1
			else:
				rw += curr / arr[i].weight * arr[i].value
				return rw
		return rw


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		frec = []
		for i in range(n):
			perUnit = arr[i].value / arr[i].weight
			frec.append([perUnit, arr[i].value, arr[i].weight])
		totalVal = 0
		frec.sort(key=lambda x: x[0], reverse=True)
		for i in range(n):
			if frec[i][2] > W:
				totalVal += W * frec[i][0]
				W = 0
			else:
				totalVal += frec[i][1]
				W = W - frec[i][2]
		return totalVal


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		rat = [[it.weight, it.value, it.value / it.weight] for it in arr]
		sor = sorted(rat, key=lambda itm: itm[2], reverse=True)
		cur_cap = W
		total_val = 0
		for i in range(n):
			if sor[i][0] <= cur_cap:
				total_val += sor[i][1]
				cur_cap -= sor[i][0]
			else:
				wt = cur_cap
				total_val += wt * sor[i][2]
				break
		return total_val


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda a: a.value / a.weight, reverse=True)
		result = 0.0
		for item in arr:
			if W == 0:
				return result
			if item.weight <= W:
				result += item.value
				W -= item.weight
			else:
				result += item.value * W / item.weight
				W = 0
		return result


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		l = []
		profit = 0
		for i in arr:
			l.append((i.value, i.weight, i.value / i.weight))
		l.sort(key=lambda x: x[2], reverse=True)
		for (i, j, k) in l:
			if j <= W:
				profit += i
				W -= j
			else:
				profit += k * W
				W = 0
				break
		return profit


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w
		self.unit = 0

class Solution:

	def fractionalknapsack(self, W, arr, n):
		for i in range(n):
			arr[i].unit = arr[i].value / arr[i].weight
		ans = 0
		arr.sort(key=lambda x: -x.unit)
		i = 0
		while i < n and W > 0:
			ans += arr[i].unit * min(arr[i].weight, W)
			W -= arr[i].weight
			i += 1
		return ans


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda x: x.value / x.weight, reverse=True)
		res = 0
		for elem in arr:
			if elem.weight <= W:
				res += elem.value
				W -= elem.weight
			else:
				res += elem.value / elem.weight * W
				return res
		return res


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		new_arr = []
		val = 0
		for i in range(n):
			compute = arr[i].value / arr[i].weight
			new_arr.append([compute, i])
		new_arr.sort(reverse=True)
		s = 0
		for i in range(n):
			y = arr[new_arr[i][1]].weight
			if W >= s + y:
				val += arr[new_arr[i][1]].value
				s += y
			else:
				val += (W - s) * new_arr[i][0]
				break
		return val


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		data = [[e.value, e.weight, e.value / e.weight] for e in arr]
		data.sort(key=lambda x: x[2], reverse=True)
		k = 0
		res = 0
		while W != 0 and k < n:
			if data[k][1] <= W:
				res += data[k][0]
				W -= data[k][1]
				k += 1
			else:
				res += data[k][2] * W
				W = 0
				break
		return res


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		new_arr = []
		for obj in arr:
			new_arr.append((obj.value / obj.weight, obj))
		new_arr.sort(key=lambda x: -x[0])
		total_value = 0
		for (per_unit_val, obj) in new_arr:
			if obj.weight <= W:
				total_value += obj.value
				W -= obj.weight
			else:
				total_value += W * per_unit_val
				W = 0
				break
		return total_value


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

	def __repr__(self):
		return '(' + str(self.value) + ',' + str(self.weight) + ')'

class Solution:

	def fractionalknapsack(self, W, arr, n):
		arr.sort(key=lambda x: x.value / x.weight, reverse=True)
		sum_value = 0.0
		curr_wt = 0.0
		for item in arr:
			if curr_wt + item.weight <= W:
				sum_value += item.value
				curr_wt += item.weight
			else:
				remain = W - curr_wt
				sum_value += item.value / item.weight * remain
				break
		return sum_value


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		new_arr = []
		for i in range(n):
			per_unit_val = arr[i].value / arr[i].weight
			new_arr.append((per_unit_val, arr[i]))
		new_arr.sort(key=lambda x: x[0], reverse=True)
		total_value = 0
		for i in range(n):
			if new_arr[i][1].weight > W:
				total_value += W * new_arr[i][0]
				W = 0
				break
			else:
				total_value += new_arr[i][1].value
				W -= new_arr[i][1].weight
		return total_value


from heapq import heapify, heappop, heappush

class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		ans = 0
		heap = []
		for i in range(n):
			a = arr[i].value / arr[i].weight
			heappush(heap, [-a, arr[i].weight])
		while heap and W > 0:
			(a, b) = heappop(heap)
			x = min(W, b)
			ans += -a * x
			W -= x
		return ans


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		d = 0
		arr.sort(key=lambda x: x.value / x.weight, reverse=True)
		for sack in arr:
			if W == 0:
				return d
			if sack.weight > W:
				d += W * (sack.value / sack.weight)
				W = 0
				break
			else:
				W -= sack.weight
				d += sack.value
		return d


class Item:

	def __init__(self, val, w):
		self.value = val
		self.weight = w

class Solution:

	def fractionalknapsack(self, W, arr, n):
		ratios = [(item.value / item.weight, item.value, item.weight) for item in arr]
		ratios.sort(reverse=True)
		total_value = 0
		remaining_weight = W
		for (ratio, value, weight) in ratios:
			if remaining_weight == 0:
				break
			elif weight <= remaining_weight:
				total_value += value
				remaining_weight -= weight
			else:
				total_value += ratio * remaining_weight
				remaining_weight = 0
		return total_value