Fractional Knapsack Problem
The Fractional Knapsack Problem maximizes value within weight capacity W when items can be split fractionally, solved optimally in O(n log n) by greedily sorting items by value-to-weight ratio.
Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code
Fractional Knapsack Problem
Unlike 0/1 Knapsack (which requires Dynamic Programming), Fractional Knapsack allows taking any fraction $0 \le f_i \le 1$ of an item. Because items are infinitely divisible, sorting items in descending order of value per unit weight ($v_i / w_i$) and greedily filling the remaining capacity is 100% optimal in $O(n \log n)$ time!
At a Glance
| Property | Fractional Knapsack | 0/1 Knapsack |
| :--- | :---: | :---: |
| Algorithm | Greedy (sort by val / wt) | Dynamic Programming |
| Time Complexity | $O(n \log n)$ | $O(n \cdot W)$ |
| Auxiliary Space | $O(1)$ extra | $O(W)$ |
---
Practice Problems
Easy
1. Classic Fractional Knapsack
Given items (weight, value) and capacity W, return the maximum total value achievable.
Approach: Sort by 1LL a.val b.wt > 1LL b.val a.wt (avoiding floating-point inaccuracy in the comparator!), then take full items until the last item is taken fractionally. Time: $O(n \log n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
struct Item { int wt, val; };
double fractionalKnapsack(int W, std::vector<Item> items) {
std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
return 1LL * a.val * b.wt > 1LL * b.val * a.wt;
});
double totalVal = 0.0;
for (const auto& it : items) {
if (W == 0) break;
int take = std::min(W, it.wt);
totalVal += static_cast<double>(take) * it.val / it.wt;
W -= take;
}
return totalVal;
}
int main() {
std::cout << std::fixed << std::setprecision(2)
<< fractionalKnapsack(50, {{10, 60}, {20, 100}, {30, 120}}) << "\n"; // 240.00
return 0;
}
</details>
Intermediate
2. Maximum Units on a Truck (LeetCode 1710)
Given box types [count, unitsPerBox] and truckSize, maximize total units loaded onto the truck.
Approach: Sort box types by unitsPerBox descending and greedily load min(truckSize, count) boxes of each type. Time: $O(n \log n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
int maximumUnits(std::vector<std::pair<int, int>> boxes, int truckSize) {
std::sort(boxes.begin(), boxes.end(), [](const auto& a, const auto& b) { return a.second > b.second; });
int units = 0;
for (const auto& [cnt, perBox] : boxes) {
int take = std::min(truckSize, cnt);
units += take * perBox;
truckSize -= take;
if (truckSize == 0) break;
}
return units;
}
int main() {
std::cout << maximumUnits({{1, 3}, {2, 2}, {3, 1}}, 4) << "\n"; // 8
return 0;
}
</details>
---
Related Algorithms
- 0/1 Knapsack Problem — DP solution when items cannot be split.
- DP vs. Greedy — when greedy works vs. fails.