Capacity To Ship Packages Within D Days

In this blog, you will learn about capacity to ship packages within d days.

Problem Statement

 

A conveyor belt has packages that must be shipped from one port to another within D days. The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship. Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days in the given order of the packages.

 

Let's take one example. The weights of the packages are [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] and the minimum number of days (D) is 5. Then, the minimum weight capacity of the ship will be 15 because, on the 1st day the packages [ 1, 2, 3, 4, 5 ] will be shipped and similarly on the 2nd day [ 6, 7 ], on the 3rd day [ 8 ] 4th day: [ 9 ] 5th day: [ 10 ]. We have another solution for the same example. That's 14 by splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) but it's not allowed since the order of the packages also needs to be maintained. Given below are some more examples for the leetcode problem,

static void Main(string[] args)
{
    int result = ShipWithinDays(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, D: 5);
    // example 1 : result = 15
    result = ShipWithinDays(new int[] { 3, 2, 2, 4, 1, 4 }, D: 3);
    // example 2 : result = 6
    result = ShipWithinDays(new int[] { 1, 2, 3, 1, 1 }, D : 4);
    // example 3 : result = 3
}

Solution

 

Our approach towards the problem is using binary search over all possible capacities of the ship for the minimum number of days. Let's discuss the algorithm in simple terms, 

1. Finding the maximum weight (i.e., shipping all the packages in one day or sum of all wieghts) and minimum weight (i.e., shipping only one package in one day or maximum of the weights) for the ship to carry in a day.
2. Start guessing for the minimum ship capacity for each day by taking the average of the maximum and minimum weight.
3. Keep incrementing the minimum weight if the number of days calculated and D is same or else decrement the maximum weight.
4. Store the best guess and as soon as the minimum becomes greater than or equal to maximum weight. 

 Here is the C# code for the algorithm given above,

public static int ShipWithinDays(int[] weights, int D)
{
    int minimumWeight = weights.Max();
    int maximumWeight = weights.Sum();

    if (TotalDaysToShip(weights, minimumWeight) <= D)
        return minimumWeight;

    int currentGuess;
    int bestGuess = -1;

    while (minimumWeight <= maximumWeight)
    {
        currentGuess = (maximumWeight + minimumWeight) / 2;
        if (TotalDaysToShip(weights, currentGuess) <= D)
        {
            bestGuess = currentGuess;
            maximumWeight = currentGuess - 1;
        }
        else
            minimumWeight = currentGuess + 1;
    }
    return bestGuess;
}
private static int TotalDaysToShip(int[] weights, int capacity)
{
    int days = 1;
    int currentShip = 0;
    foreach (int weight in weights)
    {
        if (currentShip + weight > capacity)
        {
            currentShip = 0;
            days++;
        }
        currentShip += weight;
    }
    return days;
}