DSA Capacity to Ship Packages

The problem

Capacity to Ship Packages asks for the smallest ship capacity that sends every package within a given number of days. Packages keep their order. One day carries one unbroken run of packages, and a day's total weight never exceeds the capacity.

The answer is a single number, the minimum capacity. The cases below are the ones this article tests every solution against.

cases = [
    ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5, 15),
    ([3, 2, 2, 4, 1, 4], 3, 6),
    ([1, 2, 3, 1, 1], 4, 3),
    ([5], 1, 5),
]
for weights, days, expected in cases:
    print("weights", weights, "days allowed:", days, "minimum capacity:", expected)

Read one row at a time. In the second row the answer is 6, not the heaviest package, which is 4. A capacity of 4 needs too many days, as the next section shows.

Intuition: start from the heaviest package

The first idea is to try the heaviest single package as the capacity. No smaller capacity can carry that package at all. The guess is a natural floor for the search.

The floor rarely ships in time. Each day then holds very little, and the day count climbs past the limit.

def days_for(weights, capacity):
    days = 1
    load = 0
    for weight in weights:
        if load + weight > capacity:
            days += 1
            load = weight
        else:
            load += weight
    return days

weights = [3, 2, 2, 4, 1, 4]
print("heaviest package:", max(weights))
print("days at that capacity:", days_for(weights, max(weights)))
print("days allowed:", 3)

Capacity 4 needs five days against a limit of three. The answer sits somewhere above the floor. The search for it is the real problem.

Brute force: try every capacity in order

The brute force tries each capacity from the heaviest package upward. The first capacity that ships within the limit is the answer. Trying in rising order makes the first success the smallest success.

A counter records how many capacities were tested. The count, not a clock, shows the cost.

def days_for(weights, capacity):
    days = 1
    load = 0
    for weight in weights:
        if load + weight > capacity:
            days += 1
            load = weight
        else:
            load += weight
    return days

def min_capacity_brute(weights, limit):
    tried = 0
    capacity = max(weights)
    while True:
        tried += 1
        days = days_for(weights, capacity)
        print("capacity", capacity, "days:", days, "works:", days <= limit)
        if days <= limit:
            return capacity, tried
        capacity += 1

answer, tried = min_capacity_brute([3, 2, 2, 4, 1, 4], 3)
print("answer:", answer, "capacities tried:", tried)

Three capacities were tested here, and each test walks all six packages. A wide gap between the heaviest package and the total weight means many tests. The range, not the package count, is what grows.

The optimal solution: binary search the answer

A check is monotone when a yes stays yes as the value grows, and the day-count check is monotone because a larger capacity never needs more days. That one sentence licenses a binary search over capacities instead of a step-by-step climb.

The search range runs from the heaviest package to the total weight. Each test of the middle capacity keeps the half that can still hold the answer.

def days_for(weights, capacity):
    days = 1
    load = 0
    for weight in weights:
        if load + weight > capacity:
            days += 1
            load = weight
        else:
            load += weight
    return days

def min_capacity(weights, limit):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days_for(weights, mid) <= limit:
            hi = mid
        else:
            lo = mid + 1
    return lo

cases = [
    ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5, 15),
    ([3, 2, 2, 4, 1, 4], 3, 6),
    ([1, 2, 3, 1, 1], 4, 3),
    ([5], 1, 5),
]
for weights, days, expected in cases:
    result = min_capacity(weights, days)
    print("weights", weights, "days:", days, "->", result, "expected:", expected, "match:", result == expected)

All four cases from the start of the article pass. The search never tests a capacity below the heaviest package or above the total weight. Both bounds are answers to smaller questions the reader can check by hand.

Walkthrough: weights [3, 2, 2, 4, 1, 4], three days allowed

The walk starts with lo at 4 and hi at 16. Each row tests the middle capacity and moves one bound. The range halves until the two bounds meet.

def days_for(weights, capacity):
    days = 1
    load = 0
    for weight in weights:
        if load + weight > capacity:
            days += 1
            load = weight
        else:
            load += weight
    return days

weights = [3, 2, 2, 4, 1, 4]
lo = max(weights)
hi = sum(weights)
step = 0
while lo < hi:
    step += 1
    mid = (lo + hi) // 2
    days = days_for(weights, mid)
    works = days <= 3
    print("step", step, "- range", lo, "to", hi, "- test", mid, "days:", days, "works:", works)
    if works:
        hi = mid
    else:
        lo = mid + 1
print("minimum capacity:", lo)

Four tests settle a range of thirteen capacities. The last failing test, capacity 5, pushes lo up to 6. Capacity 6 then survives as hi, and the meeting point is the answer.

Complexity

The brute force tests up to the total weight minus the heaviest package capacities, and each test walks all n packages, so its time is O(n times the weight range). The binary search tests only the logarithm of that range, so its time is O(n log of the weight range).

Both searches store only a few counters and bounds, so their extra space is O(1). The day-count walk itself stores nothing per package.

def days_for(weights, capacity):
    days = 1
    load = 0
    for weight in weights:
        if load + weight > capacity:
            days += 1
            load = weight
        else:
            load += weight
    return days

def count_tests(weights, limit, binary):
    tests = 0
    lo = max(weights)
    hi = sum(weights)
    if binary:
        while lo < hi:
            tests += 1
            mid = (lo + hi) // 2
            if days_for(weights, mid) <= limit:
                hi = mid
            else:
                lo = mid + 1
    else:
        capacity = lo
        while True:
            tests += 1
            if days_for(weights, capacity) <= limit:
                break
            capacity += 1
    return tests

for weights, limit in [([3, 2, 2, 4, 1, 4], 3), ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 2), ([2, 4, 6, 8, 10, 12, 14, 16], 3)]:
    print("packages:", len(weights), "weight range:", sum(weights) - max(weights), "brute tests:", count_tests(weights, limit, False), "binary tests:", count_tests(weights, limit, True))

On the wider ranges the binary search pulls ahead, and the gap grows with the range itself. Each halving removes half the remaining range. That is the whole gain.

Edge cases and pitfalls

A capacity below the heaviest package is not a slow case. It is an impossible one, because that package fits on no day. Any search that starts below the maximum weight can report a day count for a capacity that cannot sail.

The two extreme day limits have direct answers. One day forces the total weight. A day per package, or more, allows the heaviest package alone.

def days_for(weights, capacity):
    days = 1
    load = 0
    for weight in weights:
        if load + weight > capacity:
            days += 1
            load = weight
        else:
            load += weight
    return days

def min_capacity(weights, limit):
    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days_for(weights, mid) <= limit:
            hi = mid
        else:
            lo = mid + 1
    return lo

print("single package:", min_capacity([7], 3))
print("one day only:", min_capacity([4, 1, 4], 1))
print("a day per package:", min_capacity([4, 1, 4], 3))
print("heaviest package sets the floor:", min_capacity([1, 9, 1], 2))

The last row pairs the two light packages on one day and the heavy package on the other. Its answer is 9, the floor itself. A floor can be the answer, just never a value below it.