Log inSign up
mediumGeeksforGeeksNot Started

Fractional Knapsack

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on GeeksforGeeks
Lesson

Problem Statement

Given the weights weight[] and values val[] of N items, and a maximum knapsack capacity W. You can break items into fractions (e.g. take 50% of an item to receive 50% of its value and occupy 50% of its weight).

Find the maximum total value that can be accommodated in the knapsack.

Example 1 · Example 1: Three Items:

Input: val = [60, 100, 120], weight = [10, 20, 30], W = 50
Output: 240.00
Explanation: Ratios: item 0 = 60/10 = 6.0, item 1 = 100/20 = 5.0, item 2 = 120/30 = 4.0.\n1. Take item 0 (wt 10, val 60). Remaining W = 40. Total val = 60.\n2. Take item 1 (wt 20, val 100). Remaining W = 20. Total val = 160.\n3. Take 20/30 fraction of item 2 (val = (20/30) * 120 = 80). Remaining W = 0.\nTotal value = 60 + 100 + 80 = 240.00.

Constraints:

  • 1 <= N <= 105
  • 1 <= W <= 109
  • 1 <= val[i], weight[i] <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why fractional divisibility allows greedy choice where 0/1 knapsack requires DP.
  • Calculate and sort by value-to-weight ratio without floating point precision loss.
  • Implement the complete driver across all 4 programming languages.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Items with weight and value, knapsack capacity given.
  • Divisibility / fractional items allowed.
  • Maximizing total value.

Algorithmic Decision Tree:

  • If items can be divided -> Greedy sorting by value/weight ratio.
  • If items CANNOT be divided -> 0/1 Knapsack Dynamic Programming.

Connected Patterns:

Maximum Units on a TruckEgyptian FractionActivity Selection

1. Brute Force — Greedy by Maximum Value Alone (Flawed Baseline)

Intuition

Sort items descending by total value alone. Greedily pack items by value. Demonstrates the pitfall of prioritizing raw value over efficiency.

When to apply: Baseline comparison showing why value density is required.

Algorithm

  1. Step 1: Sort items in descending order of value.
  2. Step 2: While remaining capacity > 0 and items remain: take whole or fractional item.
  3. Step 3: Return accumulated value.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Item {
8 int value, weight;
9};
10
11class Solution {
12public:
13 double fractionalKnapsack(int w, vector<Item>& items) {
14 sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
15 return a.value > b.value;
16 });
17
18 double totalVal = 0.0;
19 int curWeight = 0;
20
21 for (const auto& item : items) {
22 if (curWeight + item.weight <= w) {
23 curWeight += item.weight;
24 totalVal += item.value;
25 } else {
26 int remain = w - curWeight;
27 totalVal += (double)item.value * ((double)remain / item.weight);
28 break;
29 }
30 }
31 return totalVal;
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
38 cout << "Max value: " << sol.fractionalKnapsack(50, items) << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting takes O(N log N). Single pass takes O(N).
  • Space complexity: O(1) auxiliary — No extra storage beyond variables.

Why Brute Force Doesn't Scale:

With N = 105, an O(N2) or recursion approach times out. O(N log N) ratio sorting runs in ~25ms.

For N = 100,000 items: O(N log N) requires ~1.7 * 106 comparisons, completing well within time limit.

2. Better — Max-Heap Priority Queue by Ratio

Intuition

Store items in a priority queue keyed on (double)value / weight. Repeatedly extract the maximum ratio item and add to knapsack. If remaining capacity is smaller than item weight, add fraction and terminate.

When to apply: When capacity fills early and full sorting is wasteful.

Algorithm

  1. Step 1: Push all items into Max-Heap ordered by ratio.
  2. Step 2: While capacity > 0 and heap not empty: pop item.
  3. Step 3: If item.weight <= capacity, add full value and subtract weight.
  4. Step 4: Else add fraction (capacity / item.weight) * item.value, set capacity = 0.
  5. Step 5: Return total value.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5using namespace std;
6
7struct Item {
8 int value, weight;
9};
10
11struct Compare {
12 bool operator()(const Item& a, const Item& b) {
13 double r1 = (double)a.value / a.weight;
14 double r2 = (double)b.value / b.weight;
15 return r1 < r2;
16 }
17};
18
19class Solution {
20public:
21 double fractionalKnapsack(int w, vector<Item>& items) {
22 priority_queue<Item, vector<Item>, Compare> pq;
23 for (const auto& item : items) pq.push(item);
24
25 double totalVal = 0.0;
26 int rem = w;
27
28 while (!pq.empty() && rem > 0) {
29 Item top = pq.top();
30 pq.pop();
31
32 if (top.weight <= rem) {
33 totalVal += top.value;
34 rem -= top.weight;
35 } else {
36 totalVal += (double)top.value * ((double)rem / top.weight);
37 rem = 0;
38 }
39 }
40 return totalVal;
41 }
42};
43
44int main() {
45 Solution sol;
46 vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
47 cout << "Max value: " << sol.fractionalKnapsack(50, items) << endl;
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(N log N) — Building heap takes O(N), extraction takes O(log N) per item.
  • Space complexity: O(N) — Priority queue stores N items.

3. Optimal — Sort by Value/Weight Ratio Descending

Intuition

Sort items by (double)val / weight descending. Iterate through sorted items: if current item completely fits in remaining capacity, take all of it. If it does not fit completely, take fraction (remaining / weight) * value and break. This is guaranteed to be optimal because every unit of weight added carries maximum possible value.

When to apply: Always for Fractional Knapsack.

Algorithm

  1. Step 1: Sort items in descending order of value / weight.
  2. Step 2: Initialize totalValue = 0.0, remaining = W.
  3. Step 3: For each item: if item.weight <= remaining, add item.value and subtract item.weight.
  4. Step 4: Else add (double)remaining / item.weight * item.value and break.
  5. Step 5: Return totalValue.

Interactive Trace for Fractional Knapsack

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Inspect Item 0 (ratio 6
Visual state
Values and pointers at this exact step
pointers
S
full (100%)
pending
pending
0
↑ current
1
2
Check / comparison
10 <= 50 (Fits completely)
Decision / next transition
Take full Item 0. Total val = 60, remaining capacity = 40.
Why this step matters

Step 1: Inspect Item 0 (ratio 6.0, weight 10, val 60). Weight 10 <= capacity 50.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7struct Item {
8 int value, weight;
9};
10
11class Solution {
12public:
13 double fractionalKnapsack(int w, vector<Item>& items) {
14 sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
15 double r1 = (double)a.value / a.weight;
16 double r2 = (double)b.value / b.weight;
17 return r1 > r2;
18 });
19
20 double totalValue = 0.0;
21 int remaining = w;
22
23 for (const auto& item : items) {
24 if (item.weight <= remaining) {
25 totalValue += item.value;
26 remaining -= item.weight;
27 } else {
28 totalValue += (double)item.value * ((double)remaining / item.weight);
29 break;
30 }
31 }
32 return totalValue;
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
39 cout << "Max value: " << sol.fractionalKnapsack(50, items) << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting takes O(N log N). Linear scan takes O(N).
  • Space complexity: O(1) auxiliary — In-place sorting uses O(1) auxiliary space beyond standard sort stack.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Greedy by Maximum Value AloneO(N log N)O(1)Sort by value descending. Fails to account for item weights, leading to suboptimal capacity usage.Wrong greedy criterion.
2.Better — Max-Heap Priority Queue by RatioO(N log N)O(N)Insert all items into a Max-Heap ordered by value/weight ratio. Repeatedly extract max ratio item until knapsack is full.Heap space overhead.
3.Optimal — Sort by Value/Weight Ratio DescendingOptimalO(N log N)O(1) auxiliarySort items by ratio (double)val / weight descending. Greedily take entire items while capacity allows; take fraction of first overflowing item.Sorting step.

Common Pitfalls & Crucial Edge Cases

Integer division in ratio comparison

In C++/Java, item.value / item.weight truncates to integer without (double) casting.

Applying greedy ratio logic to 0/1 Knapsack

Only Fractional Knapsack can be solved greedily; 0/1 Knapsack requires Dynamic Programming.

Crucial Edge Cases to Validate:

  • W = 0 — Returns 0.0.
  • Total weight of all items <= W — Take 100% of every item; return sum of all values.
  • All items have identical ratio — Any order yields identical optimal total value.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Contrast Fractional Knapsack (Greedy O(N log N)) with 0/1 Knapsack (DP O(N * W)) immediately to demonstrate conceptual depth.
  2. Be careful with floating point casting in C++ and Java when computing ratios.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does greedy value/weight ratio work for Fractional Knapsack but fail for 0/1 Knapsack?

Back to DSA Sheet