The fractional knapsack problem is solved by sorting items by value-to-weight ratio in descending order, then greedily taking as much as fits, including a final fractional slice if needed. That one-sentence rule is the entire algorithm. Given a single capacity, a list of item weights and values, and permission to break items into pieces, you sort the list, walk through it from highest ratio to lowest, take each whole item if it still fits, and on the last item that overflows the remaining capacity, take only the fraction that exactly fills the knapsack. Because the greedy rule respects a matroid-like exchange property and any leftover capacity can be exactly absorbed by splitting one item, this method is provably optimal for the fractional model — but only the fractional model. The moment items become indivisible (the 0/1 knapsack problem), the same rule can produce a strictly worse answer than a full dynamic-programming sweep. The distinction matters whenever you plan with objects you cannot cut.
What the Fractional Knapsack Problem Asks
The fractional knapsack problem starts with a knapsack of one fixed capacity W and a list of n items. Each item i has a weight w_i and a value v_i. The task is to choose how much of each item to put in the knapsack so that the total weight does not exceed W and the total value is as large as possible. Unlike most physical packing problems, the choice for each item can be any real number from zero to one — you can take the whole item, none of it, or any fraction in between.
Two consequences follow. First, the answer is always a knapsack that is filled exactly to capacity, because if any slack remained you could always fit a sliver of the next item and raise the value. Second, the fractional model is a textbook case where a greedy algorithm is provably optimal — one of the few knapsack variants with that property. Google's OR-Tools knapsack documentation describes the underlying objective as choosing a subset whose total value is maximized without exceeding capacity, the same scalar objective that drives every variant in this family.
The Greedy Algorithm Step by Step
The classical greedy procedure for fractional knapsack runs in O(n log n), with the sort dominating the cost. The steps are mechanical:
- Compute the value-to-weight ratio v_i / w_i for every item.
- Sort items in descending order by that ratio, breaking ties by input order or any fixed rule for determinism.
- Walk the sorted list. For each item, if its whole weight fits in the remaining capacity, take it entirely and subtract its weight.
- If the next item would overflow the remaining capacity, take only the fraction remaining_capacity / w_i of it. This fills the knapsack exactly and ends the algorithm.
- Sum the values of every whole item plus the fractional last piece; that sum is the optimum.
The correctness argument is short: at any step, keeping the highest remaining ratio and taking as much of it as fits cannot be improved by skipping it for a lower-ratio item, because the higher-ratio item gives at least as much value per unit of capacity consumed. Because the model allows fractions, there is always a way to absorb the last slack by splitting one item, which is what closes the proof.
A Worked Fractional Example
Suppose the knapsack has capacity W = 50, and three items are on the table:
| Item | Weight | Value | Value-to-weight ratio |
|---|---|---|---|
| X | 10 | 60 | 6.0 |
| Y | 20 | 100 | 5.0 |
| Z | 30 | 120 | 4.0 |
The ratio-sorted order is X, Y, Z. Take X in full: weight 10, remaining capacity 40, accumulated value 60. Take Y in full: weight 20 more, remaining capacity 20, accumulated value 60 + 100 = 160. Z would need 30 weight, but only 20 remain, so take a fraction 20/30 = 2/3 of Z. That fraction is worth (2/3) × 120 = 80. Total value = 60 + 100 + 80 = 240. Total weight = 10 + 20 + 20 = 50. The knapsack is full, and the greedy value 240 is the optimum for the fractional model.
The same three items under a 0/1 rule would force a different choice: you must take Z whole or not at all. Taking Z (weight 30, value 120) leaves 20 capacity, which fits Y whole (weight 20, value 100) for a total of 220. Any other combination — X+Y = 160, X+Z = 180 — is strictly worse than the fractional 240. The gap is exactly what the fractional freedom buys you.
Where Fractional Greedy Breaks Down
The greedy-by-ratio rule is optimal only when fractions are allowed. Once items must be selected whole — one row in, one row out, no splitting, no repeats — the problem becomes the 0/1 knapsack problem, and the same rule can miss the optimum. The Stanford CS161 lecture notes on 0/1 knapsack cover this point with a small counterexample: capacity 10, an item of weight 6 and value 6 (ratio 1.0), and an item of weight 5 and value 9 (ratio 1.8). The fractional answer takes the whole 5-item plus 5/6 of the 6-item for 9 + 5 = 14. The 0/1 answer must pick one or the other: picking the 5-item yields 9, picking the 6-item yields 6, and any combination exceeds capacity. In longer lists the failure is more subtle — a greedy sequence can leave capacity at the end that a slightly different combination could have used more profitably overall.
This is the practical reason the 0/1 problem is solved by dynamic programming instead: only an exact search over every subset, or an equivalent DP sweep, can prove the optimum. The Knapsack Problem Calculator implements that exact DP sweep for one capacity, up to 100 labelled items, and positive integer weights no larger than the entered capacity.
How to Solve the 0/1 Version With the Calculator
- Enter a whole-number capacity from 1 through 10,000 in the capacity field.
- Add each item as a separate row with three comma-separated fields: a unique label, a positive whole-number weight, and a value (whole or decimal, including zero).
- Double-check that no label contains a comma, no weight exceeds the capacity, no weight is zero or negative, and no value is non-finite; the calculator rejects these inputs explicitly.
- Run the solver. The result panel lists every selected label, the total value, the total weight used, and the unused capacity.
- Inspect the selection, then copy it as plain text if you want to paste it into a report or spreadsheet.
The DP behind the panel builds a table with one row per item and one column per capacity unit from 0 to your entered capacity. For each (item, capacity) cell it compares the best value achievable without the current item against the best value achievable by including it plus the best compatible earlier state, and keeps the larger. When two states tie exactly on value, the calculator retains the earlier decision rather than switching arbitrarily, so the same input always produces the same selection. After the table is filled, the solver backtracks through the recorded decisions to recover the labels that actually made the cut.
If you want a more detailed walk-through of the table mechanics, the guide on how to calculate the knapsack problem step by step expands each DP cell with a small numeric example.
What the Calculator Returns, and What It Skips
The output is deliberately inspectable. You see the chosen labels in a single block, a totals row with the value and weight, and the unused capacity at the bottom. There is no scoring system, no confidence band, no heuristic suggestion — only the proven optimum for the bounded model you entered. The selection can be copied as plain text and dropped into any document.
What the output does not contain matters just as much. It does not include physical dimensions, balance constraints, fragility, item interactions, mandatory groups, incompatible pairs, deadlines, risk, or uncertainty. The classic 10-capacity test that ships with the calculator illustrates the principle: given items with weights and values 4 and 40, and 3 and 50, the optimum selects both for value 40 + 50 = 90, rather than following a simplistic input order.
This is why the model fits cleanly for bounded scalar allocation — feature prioritization with an explicit effort budget, small portfolio examples, classroom problems, draft cut lists — but stops being appropriate the moment a constraint becomes non-scalar.
Limits of the Model and When to Stop Here
The 0/1 calculator is bounded in three ways that matter for input design. Capacity is hard-capped at 10,000 and the list at 100 unique labelled items, both to keep the table from exceeding browser memory. Weights must be whole numbers because there is one DP state per capacity unit; if your measurements have fixed decimals, scale them consistently before entry (for example, convert 2.5 kg to 25 tenths) and remember that a finer scale creates a larger table. Values may be zero or positive decimals and do not have to share a unit with weight, which lets you mix effort points, dollars, or priorities on the same row.
You should stop at the calculator's answer in cases like classroom exercises, bounded feature prioritization, draft portfolio scenarios, and small allocation problems where the weight is genuinely scalar. You should not stop there for financial portfolios with real risk, safety loading, medical resource allocation, or any decision where the scalar objective hides dependencies that change the right answer. In those cases, validate the objective, constraints, and consequences with a domain-specific model and an accountable reviewer before acting on the chosen subset.
| Use case | Fits the calculator's 0/1 model? |
|---|---|
| Feature prioritization under a fixed effort budget | Yes |
| Selecting whole crates to load a delivery truck (scalar weight) | Yes |
| Classroom 0/1 knapsack exercises | Yes |
| Portfolio optimization with risk correlations | No |
| Box packing with dimensions, balance, or stacking | No |
| Scheduling with deadlines and conflicts | No |
Once you have confirmed the problem really is a single scalar-capacity, indivisible-item selection, the Knapsack Problem Calculator gives you the provable optimum in one pass; once it is not, treat the scalar answer as a sketch and bring in a model that captures the missing dimensions.
For a deeper look, see Solve a Minimum Spanning Tree Right in Your Browser.