AntInLoop

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