Published by Dimitris Kougioumtzis · Updated
Find the least capacity that ships ordered weights in at most d contiguous days. Greedy packing supplies a monotone feasibility predicate.
Search capacities between the heaviest item and the total weight. Greedily pack each candidate capacity into contiguous days; if it uses at most the allowed days, discard larger candidates, otherwise discard smaller ones.
When to use Binary search on shipping capacity
Finding the minimum feasible resource value when feasibility is monotone.
Choosing an alternative
Ordinary binary search looks for an item in a sorted array. This view searches an implicit ordered answer space using a greedy decision procedure.
Worked example: input and state changes
Example input
7,2,5,10,8 | 2
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: Capacity lies between the heaviest item and the total weight.
State at this checkpoint
{ "values": [ 10, 32, 0, 0, 7, 0, 0, 0, 2, 0, 0, 0, 5, 0, 0, 0, 10, 0, 0, 0, 8, 0, 0, 0 ], "active": [], "kind": "matrix", "columns": 4, "rowLabels": [ "bounds", "item 0", "item 1", "item 2", "item 3", "item 4" ], "columnLabels": [ "lo / weight", "hi / day", "mid / load", "days / capacity" ], "result": 0, "output": [] }Step 7: Feasible: all larger capacities are feasible too.
State at this checkpoint
{ "values": [ 10, 32, 21, 2, 7, 1, 7, 21, 2, 1, 9, 21, 5, 1, 14, 21, 10, 2, 10, 21, 8, 2, 18, 21 ], "active": [], "kind": "matrix", "columns": 4, "rowLabels": [ "bounds", "item 0", "item 1", "item 2", "item 3", "item 4" ], "columnLabels": [ "lo / weight", "hi / day", "mid / load", "days / capacity" ], "result": 0, "output": [] }Step 15: Probe capacity 18.
State at this checkpoint
{ "values": [ 16, 21, 18, 0, 7, 1, 7, 15, 2, 1, 9, 15, 5, 1, 14, 15, 10, 2, 10, 15, 8, 3, 8, 15 ], "active": [ 2 ], "kind": "matrix", "columns": 4, "rowLabels": [ "bounds", "item 0", "item 1", "item 2", "item 3", "item 4" ], "columnLabels": [ "lo / weight", "hi / day", "mid / load", "days / capacity" ], "result": 0, "output": [] }Step 22: Probe capacity 17.
State at this checkpoint
{ "values": [ 16, 18, 17, 0, 7, 1, 7, 18, 2, 1, 9, 18, 5, 1, 14, 18, 10, 2, 10, 18, 8, 2, 18, 18 ], "active": [ 2 ], "kind": "matrix", "columns": 4, "rowLabels": [ "bounds", "item 0", "item 1", "item 2", "item 3", "item 4" ], "columnLabels": [ "lo / weight", "hi / day", "mid / load", "days / capacity" ], "result": 0, "output": [] }Step 29: Minimum capacity 18; assignment uses 2 days.
State at this checkpoint
{ "values": [ 18, 18, 18, 2, 7, 1, 7, 18, 2, 1, 9, 18, 5, 1, 14, 18, 10, 2, 10, 18, 8, 2, 18, 18 ], "active": [], "kind": "matrix", "columns": 4, "rowLabels": [ "bounds", "item 0", "item 1", "item 2", "item 3", "item 4" ], "columnLabels": [ "lo / weight", "hi / day", "mid / load", "days / capacity" ], "result": 18, "output": [ 1, 1, 1, 2, 2 ] }
Expected final state
Minimum capacity 18; assignment uses 2 days.
Complexity and input bounds
Family: Searching. Time complexity: O(n log(sum weights)).
Implementation detail: At most sixteen positive integer weights and a day count from one through n keep arithmetic bounded. Matrix rows show search bounds and each item day/load under a probed capacity. Downloads return minimum capacity and serialize the final one-based greedy day assignment.
Space complexity: O(1) auxiliary predicate state excluding the day-assignment output and recorded 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..16 positive weights 1..99 | days 1..n. Keep item order; empty days are allowed.
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
Preserve item order and count a new day only when the next weight exceeds capacity. Feasibility means at most d days; unused empty days are allowed. The lower bound must fit the heaviest item.
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 | // Positive weights 1..99, n 1..16, days 1..n; order must be preserved and at most days contiguous groups are used. Returns minimum integer shipping capacity. Writes one-based greedy day assignment for each item, output capacity n. Empty download input n=0,days=0 returns 0 and writes nothing. Monotone feasibility is greedy packing; binary search spans max weight through sum weights. O(n*log(sum weights)) time, O(1) scratch excluding output. 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(a, n, days, output) { if (n == 0) { return 0; } let low = 0; let high = 0; let mid = 0; let used = 0; let load = 0; for (let i = 0; i < n; i++) { if (a[i] > low) { low = a[i]; } high += a[i]; } while (low < high) { mid = (low+high) >> 1; used = 1; load = 0; for (let i = 0; i < n; i++) { if (load+a[i] > mid) { used++; load = 0; } load += a[i]; } if (used <= days) { high = mid; } else { low = mid+1; } } used = 1; load = 0; for (let i = 0; i < n; i++) { if (load+a[i] > low) { used++; load = 0; } load += a[i]; output[i] = used; } return low; } |
Source
Reference text for binary search, not an asserted original paper for this shipping example. The playground applies the method to a monotone greedy feasibility predicate.
- The Art of Computer Programming, Volume 3: Sorting and Searching (2nd edition)
Donald E. Knuth (1998). Reference book.