Skip to main content
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...