Published by Dimitris Kougioumtzis · Updated
Take items in decreasing value/weight ratio. The last item may be fractional; exact numerator and denominator avoid rounding in every language.
Order items by decreasing value per unit weight using exact cross products. Take each item completely while capacity permits, then take the remaining weight from the next item.
When to use Fractional knapsack
Allocating a divisible resource when item value grows linearly with the amount taken.
Choosing an alternative
Zero-one knapsack cannot split an item and needs a different optimization method. Fractional knapsack permits a partial final item, making the ratio-based greedy choice optimal.
Worked example: input and state changes
Example input
60,100,120 | 10,20,30 | 50
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Sort ratios by cross multiplication; equal ratios keep input order.
State at this checkpoint
{ "values": [ 60, 10, 0, "0/10", 100, 20, 0, "0/20", 120, 30, 0, "0/30" ], "active": [], "kind": "matrix", "columns": 4, "columnLabels": [ "value", "weight", "taken weight", "fraction" ], "result": 0, "denominator": 1, "output": [ 1, 0, 0, 0 ] }Step 1: Take all of item 0.
State at this checkpoint
{ "values": [ 60, 10, 10, "10/10", 100, 20, 0, "0/20", 120, 30, 0, "0/30" ], "active": [ 2 ], "kind": "matrix", "columns": 4, "columnLabels": [ "value", "weight", "taken weight", "fraction" ], "result": 60, "denominator": 1, "output": [ 1, 10, 0, 0 ] }Step 2: Take all of item 1.
State at this checkpoint
{ "values": [ 60, 10, 10, "10/10", 100, 20, 20, "20/20", 120, 30, 0, "0/30" ], "active": [ 6 ], "kind": "matrix", "columns": 4, "columnLabels": [ "value", "weight", "taken weight", "fraction" ], "result": 160, "denominator": 1, "output": [ 1, 10, 20, 0 ] }Step 3: Take fraction 20/30 of item 2.
State at this checkpoint
{ "values": [ 60, 10, 10, "10/10", 100, 20, 20, "20/20", 120, 30, 20, "20/30" ], "active": [ 10 ], "kind": "matrix", "columns": 4, "columnLabels": [ "value", "weight", "taken weight", "fraction" ], "result": 7200, "denominator": 30, "output": [ 30, 10, 20, 20 ] }Step 4: Optimal total value 7200/30 exactly.
State at this checkpoint
{ "values": [ 60, 10, 10, "10/10", 100, 20, 20, "20/20", 120, 30, 20, "20/30" ], "active": [], "kind": "matrix", "columns": 4, "columnLabels": [ "value", "weight", "taken weight", "fraction" ], "result": 7200, "denominator": 30, "output": [ 30, 10, 20, 20 ] }
Expected final state
Optimal total value 7200/30 exactly.
Complexity and input bounds
Family: Optimization. Time complexity: O(n^2) bounded ratio sorting.
Implementation detail: Up to eight values 0..999, weights 1..99 and capacity 0..99. Downloads return an exact numerator and write its denominator plus taken weight per original item. The fraction may be unreduced; the objective is numerator divided by denominator. This representation avoids cross-language floating-point rounding.
Space complexity: O(n) order and allocation storage, plus recorded matrix frames.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
1..8 values 0..999 | matching positive weights 1..99 | capacity 0..99. Output represents an exact, possibly unreduced fraction.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Do not sort only by item value or only by weight. Keep original item indices when reporting allocations. Positive weights are required, and equal ratios use a fixed input-order tie rule.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 | // Fractional knapsack: n 0..8 values 0..999, positive weights 1..99, capacity 0..99. Returns exact objective numerator; output[0] is its positive denominator and output[1..n] gives weight units taken from each original item. Value is numerator/output[0]; fraction need not be reduced. Output capacity n+1. Ratios sorted by exact cross products, equal ratios preserve input order. At most one item is partial. Empty input returns 0 with denominator 1. Invalid bounds return -1 (output unspecified). No input mutation. O(n^2) ratio insertion sort, O(n) scratch. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(values, weights, n, capacity, output) { if (n < 0 || n > 8 || capacity < 0 || capacity > 99) { return -1; } output[0] = 1; for (let i = 0; i < n; i++) { output[i+1] = 0; if (weights[i] < 1 || weights[i] > 99 || values[i] < 0 || values[i] > 999) { return -1; } } let order = Array(256).fill(0); let key = 0; let cursor = 0; let remaining = capacity; let numerator = 0; let denominator = 1; let index = 0; for (let i = 0; i < n; i++) { order[i] = i; } for (let i = 1; i < n; i++) { key = order[i]; cursor = i-1; while (cursor >= 0 && values[order[cursor]]*weights[key] < values[key]*weights[order[cursor]]) { order[cursor+1] = order[cursor]; cursor--; } order[cursor+1] = key; } for (let i = 0; i < n; i++) { if (remaining == 0) { break; } index = order[i]; if (remaining >= weights[index]) { output[index+1] = weights[index]; remaining -= weights[index]; numerator += values[index]; } else { output[index+1] = remaining; numerator = numerator*weights[index]+values[index]*remaining; denominator = weights[index]; remaining = 0; } } output[0] = denominator; return numerator; } |
Source
Related primary research on discrete optimization and linear-programming relaxations. This does not assert an original-paper attribution for the simple fractional greedy rule; the playground solves the divisible-item relaxation.
- Discrete-Variable Extremum Problems
George B. Dantzig (1957). Related knapsack and linear-programming research.