Fractional Knapsack
This problem was taken from the Coursera Data Structures and Algorithms Specialization, specifically from the Algorithmic Toolbox Course, Week 3:Greedy Algorithms, that I’ve recently completed. If you are taking that course or plan to take that course, please don’t look ahead at the solution as it will be against the Honor Code and won’t do you any good.
Problem Introduction
Given a set of items and total capacity of a knapsack, find the maximal value of fractions of items that fit into the knapsack.
Problem Description
Task: The goal of this code problem is to implement an algorithm for the fractional knapsack problem.
Input Format: The first line of the input contains the number n of items and the capacity W of a knapsack.
The next n lines define the values and weights of the items. The i-th line contain integers v(i) and w(i) — the value and the weight of i-th item, respectively.
Constraints: 1 ≤ n ≤ 10^3 , 0 ≤ W ≤ 2 · 10^6 ; 0 ≤ v(i) ≤ 2 · 106 ,
0 < w(i) ≤ 2 · 10^6 for all 1 ≤ i ≤ n. All the numbers are integers.
Output Format: Output the maximal value of fractions of items that fit into the knapsack. The absolute value of the difference between the answer of your program and the optimal value should be at most 10 −3 . To ensure this, output your answer with at least four digits after the decimal point (otherwise your answer, while being computed correctly, can turn out to be wrong because of rounding issues).
Time Limits: C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.
Memory Limit: 512 Mb
Sample 1
Input:
3 50
60 20
100 50
120 30
Output:
180.0000
Explanation:
To achieve the value 180, we take the first item and the third item into the bag.
Sample 2
Input:
1 10
500 30
Output:
166.6667
Explanation:
Here, we just take one third of the only available item
My Solution:
If you can think of any other way to improve this algorithm or if you could point out something that you think I did wrong, you’re more than welcome to reach out to me by responding to this and pointing out the mistakes. If you like this solution, please hit the “Recommend” button below, it’ll mean a lot to me. Thanks.
