What is the brute force approach and complexity for Fractional Knapsack?

Try every order of the items; fill the bag in that order and keep the best total with time complexity O(N! · N) and space complexity O(N).

What is the optimal approach and complexity for Fractional Knapsack?

Sort by value ÷ weight, highest first; take whole items, then one fraction with optimal time complexity O(N log N) and space complexity O(N).

How do you identify the pattern for Fractional Knapsack?

Look for key signals in the prompt: "value and weight of each item" indicates Each item has a rate: value per kg. The rate decides the order.; "you may cut an item" indicates Any kilogram of a good item can be taken. That is why greedy is safe here.; "largest total value within the capacity" indicates A fill-the-bag problem: pack the best rate first..

Fractional Knapsack

Easy·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelGreedy: sort by value per kg (exchange argument)

Complexity:O(N! · N)→O(N log N)

Key Insight

Sort the items by value per kg, highest first. Walk down the list and take each item whole while it fits. The first item that does not fit is cut: take only the fraction that fills the rest of the bag, then stop.

Core Validity Invariant

An item can go in only while the bag has room, and the total weight must never go over capacity. We take the whole item if it fits, and only room kg of it if it does not.

Problem

You have a bag that can hold at most capacity kg. Each item has a value and a weight.

You may cut an item. If you take 2/3 of an item, you get 2/3 of its value. Fill the bag so the total value is as large as possible.

Return that total as a decimal number, rounded to 6 decimal places.

Input

Two arrays val and wt of the same length (value and weight of each item), and an integer capacity.

Output

One decimal number: the largest total value you can carry, rounded to 6 decimal places (for example 240.000000).

Example 1

Input: val = [60, 100, 120], wt = [10, 20, 30], capacity = 50

Output: 240.000000

Take the whole 10 kg and 20 kg items (60 + 100). That leaves 20 kg. Take 20/30 of the 30 kg item: 120 × 20/30 = 80. Total 240.

Example 2

Input: val = [500], wt = [30], capacity = 10

Output: 166.666667

Only 10 of the 30 kg fit, so take 10/30 of the item: 500 × 10/30 = 166.666…, which rounds to 166.666667.

Constraints

• The number of items is at most 10^5, and `val` and `wt` have the same length.
• 1 ≤ val[i], wt[i] ≤ 10^4
• 1 ≤ capacity ≤ 10^9

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If you can only take part of an item, how much value does the part give you?
2.
Would you rather fill the bag with an item that has a big value, or one that has a big value per kg? Why?
3.
If the best item is light, what happens to the room you have left for the next item?
4.
Could a small piece of a worse item plus more of a better item ever beat the plain choice? Try it on paper.
5.
What would change if you could not cut items at all? Would the same plan still work?

Brute force approach

Idea

An order of the items decides how the bag is filled. Walk down the order, take each item whole if it fits, and cut the first item that does not fit. Try all N! orders and keep the best total. The best order is among them, so the best total is the answer.

Thinking process

1
I don't know the right order, so I can try every order.
2
For one order, go down the list: take each item whole while it fits. When an item is too big for the room left, take the part that fits.
3
Check with val = [60, 100, 120], wt = [10, 20, 30], capacity 50. The order 0, 1, 2 takes the 10 kg and 20 kg items whole (room 20 left), then 20/30 of the 120 item = 80. Total 240.
4
The order 2, 0, 1 takes the 120 item whole (30 kg, room 20), then the 60 item (10 kg, room 10), then 10/20 of the 100 item = 50. Total 230. That order is worse.
5
Keep the largest total over all orders.

Code & Implementation

brute.cpp

class Solution {
public:
    double fractionalKnapsack(vector<int>& val, vector<int>& wt, int capacity) {
        int n = val.size();
        vector<int> order(n);
        iota(order.begin(), order.end(), 0);
        double best = 0;
        // Try every order of the items. For each one, fill the bag greedily in that order.
        do {
            long long room = capacity;
            double total = 0;
            for (int i : order) {
                if (room == 0) break;
                if (wt[i] <= room) {
                    // Whole item fits.
                    total += val[i];
                    room -= wt[i];
                } else {
                    // Only part of it fits.
                    total += (double)val[i] * room / wt[i];
                    room = 0;
                }
            }
            best = max(best, total);
        } while (next_permutation(order.begin(), order.end()));
        return round(best * 1e6) / 1e6;
    }
};

Complexity

Time O(N! · N)Space O(N)

There are N! orders, and filling the bag in one order takes N steps. Fine for N ≤ 8, far too slow for 10^5. The space is the order array.

Optimized approach

Idea

Start from brute force

Brute force tries every order. Only one order matters: the order by value per kg. Once that is known, one walk fills the bag.

Find the repeated work

Every order fills the bag from scratch. For the best order, each choice is already known: the item with the highest value per kg that is left.

Define the state — what variables do I need?

room: Kilograms still free in the bag. Starts at capacity.
total: Value collected so far. It is a decimal number, because of the cut item.
i: Position in the list sorted by value per kg, best first.

Define validity

An item can go in only while the bag has room, and the total weight must never go over capacity. We take the whole item if it fits, and only room kg of it if it does not.

Define the transitions — when does each pointer move, and why is it safe?

wt ≤ room

total += val; room -= wt

The whole item fits. It has the best value per kg of anything left, so taking all of it is never worse.

wt > room

total += val × room ÷ wt; room = 0

Only part of this item fits. That part is worth the best rate still available, and the bag is now full, so we stop.

room = 0

stop

Nothing else can add value, because the bag has no room left.

What does the current window add to the answer?

Each item adds its value for the kilograms we take: all of val for a whole item, or val × room ÷ wt for the cut one.

Code & Implementation

optimal.cpp

class Solution {
public:
    double fractionalKnapsack(vector<int>& val, vector<int>& wt, int capacity) {
        int n = val.size();
        vector<int> idx(n);
        iota(idx.begin(), idx.end(), 0);
        // Highest value per kg first. Compare val_a / wt_a with val_b / wt_b by
        // cross-multiplying (weights are positive), so no division can lose precision.
        sort(idx.begin(), idx.end(), [&](int a, int b) {
            return (long long)val[a] * wt[b] > (long long)val[b] * wt[a];
        });

        double total = 0;
        long long room = capacity;
        for (int i : idx) {
            if (room == 0) break;
            if (wt[i] <= room) {
                // Whole item fits: its value per kg is the best left, so take all of it.
                total += val[i];
                room -= wt[i];
            } else {
                // Only room kg fit: take that fraction of the value.
                total += (double)val[i] * room / wt[i];
                room = 0;
            }
        }
        // The problem asks for 6 decimal places.
        return round(total * 1e6) / 1e6;
    }
};

Complexity

Time O(N log N)Space O(N)

Sorting costs O(N log N). The walk is one pass. The index array used for sorting takes O(N) extra space.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Try every order of the items; fill the bag in that order and keep the best total	O(N! · N)	O(N)
Optimal	Sort by value ÷ weight, highest first; take whole items, then one fraction	O(N log N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“value and weight of each item”Each item has a rate: value per kg. The rate decides the order.
“you may cut an item”Any kilogram of a good item can be taken. That is why greedy is safe here.
“largest total value within the capacity”A fill-the-bag problem: pack the best rate first.

Sort by value ÷ weight+Take whole items while they fit+Cut one item for the rest of the room→Greedy: sort by value per kg (exchange argument)

This is the anchor of the sort + exchange sub-pattern. The key choice is the sort key: value per kg, not value and not weight alone. Because items can be cut, a kilogram of the best rate always beats a kilogram of a worse rate, and the exchange argument shows that swapping kilograms never hurts. The next problems in this sub-pattern sort by a deadline or a height, because they have no rates and no cutting.

Don't make this mistake

Pattern confusion: using the 0/1 Knapsack rule (whole items only)

✗ // Greedy by ratio, but skip any item that does not fit whole

✓ // Cut the first item that does not fit (fractional knapsack)

Without cutting, the greedy gets stuck. With val = [60, 100, 120], wt = [10, 20, 30], capacity 50, the greedy takes 10 kg and 20 kg (160), and the 30 kg item does not fit. The best whole-item choice is 100 + 120 = 220 (20 kg + 30 kg). Cutting is what makes the greedy correct. Without cutting, you need DP.

Sorting by value instead of value per kg

✗ sort(idx.begin(), idx.end(), [&](int a, int b) { return val[a] > val[b]; });

✓ sort(idx.begin(), idx.end(), [&](int a, int b) { return (long long)val[a] * wt[b] > (long long)val[b] * wt[a]; });

On the first example, sorting by value takes 120 (30 kg) first, then 100 (20 kg). That fills 50 kg exactly, for a total of 220. Sorting by value per kg takes 60 (10 kg), 100 (20 kg), then 20/30 of 120 = 80, for 240.

Sorting by the lightest weight

✗ sort by wt[a] < wt[b]

✓ sort by val ÷ wt, highest first

Take val = [2, 30], wt = [1, 10], capacity 10. Lightest first takes the 1 kg item (value 2), then 9/10 of the 30 item = 27, for 29. The per-kg order takes the 30 item whole (10 kg), for 30. Light is not the same as good.

Integer division when computing the ratio or the cut

✗ int ratio = val[i] / wt[i]; // 7/3 = 2 and 5/2 = 2: a tie int part = val[i] * room / wt[i];

✓ Compare with cross-multiplication, and compute the cut as (double)val[i] * room / wt[i]

Take A = (value 7, weight 3) and B = (value 5, weight 2). The real rates are 2.33 and 2.5, so B comes first. The integer rates are both 2, so the order can flip. With capacity 3 and A first, the total is 7. The correct total is B whole (5) plus 1/3 of A (2.33) = 7.33.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Greedy translate into production architectures and low-level memory mechanics.

LLD Architecture