Binary Search for Ship Capacity in Python

Use binary search to find the minimum ship capacity that can transport all packages within a given number of days.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 13 views 0 copies

binary search greedy capacity simulation algorithm

Python code

26 lines

Python 3.9+

def ship_within_days(weights, days):
    def can_ship(capacity):
        current = 0
        needed_days = 1
        for weight in weights:
            if current + weight > capacity:
                needed_days += 1
                current = 0
            current += weight
        return needed_days <= days

    low = max(weights)
    high = sum(weights)
    while low < high:
        mid = (low + high) // 2
        if can_ship(mid):
            high = mid
        else:
            low = mid + 1
    return low

if __name__ == "__main__":
    weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    days = 5
    result = ship_within_days(weights, days)
    print(f"Minimum capacity for {days} days: {result}")

Output

stdout

Minimum capacity for 5 days: 15

How it works

The solution treats the minimum capacity as the lower bound max(weights) because a ship must carry at least the heaviest package. The upper bound is sum(weights) where the ship takes everything in one trip. The can_ship function simulates loading packages sequentially, incrementing the day count when adding a package would exceed capacity. Binary search narrows the range until low equals high, the smallest capacity that satisfies the day constraint.

Common mistakes

Forgetting capacity must be at least the maximum weight, causing invalid lower bound.
Using `sum(weights) // days` as the lower bound, which may be below the max package weight.
Off-by-one errors in binary search, like using `mid = (low + high)` without the floor division.

Variations

Use a greedy simulation with `math.ceil` to compute days directly for a given capacity.
Implement with a `while True` loop and track the last feasible capacity.

Real-world use cases

Logistics companies find the minimal truck capacity to deliver all goods within a deadline.
Cloud storage services split large uploads into chunks, scheduling them across available time slots.
Manufacturers batch production orders into daily runs to meet shipping targets.

Binary Search for Ship Capacity in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes