Back to ChallengesFractional KnapsackMedium 30 min

Fractional Knapsack

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. Unlike 0/1 knapsack, you are allowed to break the item.

Examples

Input: W = 50, values = [60, 100, 120], weights = [10, 20, 30]

Output: 240

Take item 1 (value 60, weight 10), item 2 (value 100, weight 20), and 2/3 of item 3 (value 80, weight 20).

Constraints

• 1 <= N <= 10^5
• 1 <= W <= 10^9
• 1 <= values[i], weights[i] <= 10^4

Complexity Analysis

Time

O(N log N)

due to sorting the items.

Space

O(N)

to store item objects.

Test Cases

#1 Standard case

Input: W = 50, values = [60,100,120], weights = [10,20,30]

Expected: 240

#2 Single item fraction

Input: W = 10, values = [500], weights = [30]

Expected: 166.67

Output

Click "Run Code" to see output here...