Fractional Knapsack Problem

Geeks for Geeks [Medium]

Problem Statement

Given weights and values of n items, put these items in a knapsack of capacity W to get maximum total value. Items can be broken into fractions.

Example: Items = [(60,10),(100,20),(120,30)], W = 50 → Output: 240

Approach 1: Brute Force

Try all subsets and fractions to maximize value.

Time Complexity: O(2^n)

Space Complexity: O(n)

for each subset of items:
    for each possible fraction of items:
        if total weight <= W:
            calculate value
return maximum value

💡 Think: Enumerate subsets and fractions to maximize value under capacity—impractical but conceptually complete.

Approach 2: Better

Sort items by value/weight ratio and pick fractionally.

Time Complexity: O(n log n)

Space Complexity: O(n)

sort items by value/weight ratio descending
totalValue = 0
for each item in sorted list:
    if item.weight <= W:
        take full item
        W -= item.weight
        totalValue += item.value
    else:
        take fraction W/item.weight
        totalValue += item.value * W/item.weight
        break
return totalValue

💡 Think: Pick items in decreasing value/weight; take whole items, then the fraction that fits.

Approach 3: Optimal Greedy

Use priority queue or sorting by value/weight ratio to maximize value efficiently.

Time Complexity: O(n log n)

Space Complexity: O(n)

create max-heap by value/weight ratio
totalValue = 0
while W > 0 and heap not empty:
    item = pop heap
    if item.weight <= W:
        take full item
        W -= item.weight
        totalValue += item.value
    else:
        take fraction W/item.weight
        totalValue += item.value * W/item.weight
        W = 0
return totalValue

💡 Think: Use a max-heap by value/weight to repeatedly take the most efficient remaining item.

Solve on LeetCode