Maximizing Fractional Values — Problem Statement & Solution Guide
Problem Description
Given a set of items, each with a value and a weight, determine the subset of these items to include in a collection of limited capacity that maximizes the total value, considering fractional values.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximizing Fractional Values"
WHY DOES IT MATTER?
The fractional knapsack pattern exemplifies how greedy choices can be provably optimal when the problem exhibits a matroid structure, teaching candidates to recognize when sorting by a ratio leads to linear‑time solutions instead of exponential or DP approaches.
OPTIMIZATION CHALLENGE
The key insight is that sorting by value‑to‑weight ratio reduces the combinatorial search space to a single linear pass, turning an otherwise exponential subset selection into O(n log n) time, which is the lower bound for any comparison‑based solution.
REAL-WORLD CONNECTION
In cloud resource allocation, you often distribute limited CPU or memory among jobs based on their profit‑per‑resource ratio; the greedy fill mirrors how schedulers maximize revenue while respecting capacity constraints.
During an interview, compute the density on the fly while reading input, store items in an array, use a stable sort if tie‑breaking matters, and break early once the capacity is filled to avoid unnecessary iterations.
COMPLEXITY AT A GLANCE
O(n log n)O(n)Core Theory — Why This Approach?
The fractional knapsack problem asks for the maximum total value achievable when we can take any fraction of an item, given a weight capacity. The optimal greedy strategy sorts items by their value‑to‑weight ratio (density) in descending order and then picks items in that order, taking whole items while the remaining capacity permits and a final fractional piece of the next item if needed. This works because the objective function is linear and the feasible region is a matroid; any exchange that replaces a lower‑density item with a higher‑density one strictly improves the solution, guaranteeing that the greedy choice is globally optimal.
Naïve approaches, such as trying every subset of items (2^n) or using dynamic programming like the 0/1 knapsack, explode combinatorially and cannot handle the typical input sizes (n up to 10^5, capacities up to 10^9) within time limits. Moreover, DP assumes indivisible items, so it yields sub‑optimal values for the fractional variant. The greedy paradigm leverages the problem’s continuous nature, reducing the decision to a simple sort followed by a linear scan, achieving O(n log n) time, which is optimal for comparison‑based sorting.
The underlying theory also connects to linear programming duality: the fractional knapsack is a special case of a linear program with a single constraint, whose optimal solution lies at a vertex of the feasible polytope. The greedy algorithm directly constructs that vertex by saturating the capacity with the highest‑density items first. Hence, the greedy method is not only intuitive but provably optimal for this class of problems.
Interview Questions on This Problem
Q1How would you modify the fractional knapsack solution if each item also had a maximum allowable fraction (e.g., you can take at most 30% of a particular item)?
Sort items by density as usual, then during the scan respect both the remaining capacity and the per‑item fraction limit: take min(remaining capacity, weight * maxFraction) of the current item. This still runs in O(n log n) because the ordering does not change.
Q2Explain why the greedy algorithm fails for the 0/1 knapsack problem but succeeds for the fractional version.
In 0/1 knapsack, taking a high‑density item may block the inclusion of a combination of lower‑density items that together yield higher total value, violating the optimal substructure needed for greedy correctness. Fractional knapsack’s linear objective and single constraint ensure that any local density improvement leads to a global optimum, satisfying the matroid property.
Q3A company wants to maximize profit from advertising slots where each slot has a revenue per second and a maximum duration you can purchase. How does this map to the fractional knapsack, and what would be your implementation steps?
Treat each slot as an item with value = revenue per second * maxDuration and weight = maxDuration. The capacity is the total ad time you can buy. Sort slots by revenue per second (density) and fill the total time with whole slots until you run out, then take a fractional part of the next slot. Implementation: compute density, sort, iterate, accumulate value, break when capacity exhausted.
Examples
Input
values = [10, 5, 8], weights = [2, 1, 3], capacity = 4
Output
17.5
Explanation: Given the items with values [10, 5, 8] and weights [2, 1, 3], and a capacity of 4, we select the item with value 10 and weight 2. The remaining capacity is 2. We can take the fraction of the item with value 5 and weight 1, which is 2/1. The total value is 10 + 5 = 15. We still have capacity left, so we can take the fraction of the item with value 8 and weight 3, which is 2/3. The total value is 15 + (8*2)/3 = 17.5.
Input
values = [20, 15, 12], weights = [4, 3, 2], capacity = 6
Output
35
Explanation: Given the items with values [20, 15, 12] and weights [4, 3, 2], and a capacity of 6, we select the item with value 20 and weight 4. The remaining capacity is 2. We can take the item with value 15 and weight 3. The total value is 20 + 15 = 35.
Constraints
- 1 ≤ number of items ≤ 100
- 1 ≤ weight of each item ≤ 1000
- 1 ≤ capacity ≤ 1000
- All values and weights are non-negative integers
Optimal Approach & Strategy
Sort items by value‑to‑weight ratio and linearly scan, taking whole items while possible and a final fractional piece, achieving O(n log n) time.
Brute Force Approach
Enumerate every subset of items and for each compute the best fractional fill, which is exponential (2^n) and infeasible for large n.
Verified Code Solutions
function fractionalKnapsack(values, weights, capacity) {
let ratio = values.map((value, index) => value / weights[index]);
let sortedIndices = Array.from(Array(values.length).keys()).sort((a, b) => ratio[b] - ratio[a]);
let totalValue = 0;
for (let i = 0; i < sortedIndices.length; i++) {
let index = sortedIndices[i];
if (weights[index] <= capacity) {
totalValue += values[index];
capacity -= weights[index];
} else {
let fraction = capacity / weights[index];
totalValue += values[index] * fraction;
break;
}
}
return totalValue;
}class Solution {
public:
double fractionalKnapsack(vector<int> values, vector<int> weights, double capacity) {
vector<double> ratio(values.size());
for (int i = 0; i < values.size(); i++) {
ratio[i] = (double) values[i] / weights[i];
}
vector<int> sortedIndices(values.size());
for (int i = 0; i < values.size(); i++) {
sortedIndices[i] = i;
}
sort(sortedIndices.begin(), sortedIndices.end(), [&](int a, int b) { return ratio[b] > ratio[a]; });
double totalValue = 0;
for (int i = 0; i < sortedIndices.size(); i++) {
int index = sortedIndices[i];
if (weights[index] <= capacity) {
totalValue += values[index];
capacity -= weights[index];
} else {
double fraction = capacity / weights[index];
totalValue += values[index] * fraction;
break;
}
}
return totalValue;
}
};class Solution {
public double fractionalKnapsack(int[] values, int[] weights, double capacity) {
double[] ratio = new double[values.length];
for (int i = 0; i < values.length; i++) {
ratio[i] = (double) values[i] / weights[i];
}
int[] sortedIndices = new int[values.length];
for (int i = 0; i < values.length; i++) {
sortedIndices[i] = i;
}
Arrays.sort(sortedIndices, (a, b) -> Double.compare(ratio[b], ratio[a]));
double totalValue = 0;
for (int i = 0; i < sortedIndices.length; i++) {
int index = sortedIndices[i];
if (weights[index] <= capacity) {
totalValue += values[index];
capacity -= weights[index];
} else {
double fraction = capacity / weights[index];
totalValue += values[index] * fraction;
break;
}
}
return totalValue;
}
}def fractional_knapsack(values, weights, capacity):
ratio = [value / weight for value, weight in zip(values, weights)]
sorted_indices = sorted(range(len(values)), key=lambda i: ratio[i], reverse=True)
total_value = 0
for i in sorted_indices:
if weights[i] <= capacity:
total_value += values[i]
capacity -= weights[i]
else:
fraction = capacity / weights[i]
total_value += values[i] * fraction
break
return total_valuefunction fractionalKnapsack(values, weights, capacity) {
let ratio = values.map((value, index) => value / weights[index]);
let sortedIndices = Array.from(Array(values.length).keys()).sort((a, b) => ratio[b] - ratio[a]);
let totalValue = 0;
for (let i = 0; i < sortedIndices.length; i++) {
let index = sortedIndices[i];
if (weights[index] <= capacity) {
totalValue += values[index];
capacity -= weights[index];
} else {
let fraction = capacity / weights[index];
totalValue += values[index] * fraction;
break;
}
}
return totalValue;
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.