Binary Search Based : Ship packages

Binary search based problem : Ship all the packages with given weights in D days.

Given:
N number of packages are to be shipped.
Each package ‘x’ from 1 .. N has weight W [ x ].

Shipping criteria
Criteria 1 : Ship all the packages.
Criteria 2 : Ship all the packages in continuous order.
Criteria 3 : Ship all the packages in exactly D days.

Goal is to find a ship with minimum capacity that will ship all the packages within D days.


Idea for shipping packages problem using binary search

Case a) If the number of packages to be shipped is 0, then the minimum capacity of the ship is 0.

Case b) If the number of packages equal the number of days D to be shipped in, then the minimum capacity of the ship is maximum of ( W [ 1 ], W [ 2 ], … W [ N ] ).

Case c) Use binary search to find the minimum capacity of the ship for shipping N weight in exactly D days
Example :
Consider 4 packages with weights [ 1, 2, 3, 4 ] to be shipped in 2 days.
Choose a ship with very large capacity say a number (INT_MAX).

Binary_Search_Ship_Package

Beg End Mid
(Capacity of ship in kg)
Day 1 Day 2 Package on days
0 100 50 1 + 2 + 3 + 4
(All 4 packages)
0 (Package) 4 (Day 1). More packages got shipped on Day 1.
So continue binary search with smaller capacity ship i.e (50-1) / 2
0 49 24 1 + 2 + 3 + 4
(All 4 packages)
0 (No package) 4 (Day 1). More packages got shipped on Day 1.
So continue binary search with smaller capacity ship i.e 24-1 / 2
0 23 11 1 + 2 + 3 + 4
(All 4 packages)
0 (No package) 1 (Student 1). 4 (Day 1). More packages got shipped on Day 1.
So continue binary search with smaller capacity ship i.e 11-1 / 2
0 10 5 1 + 2
(2 packages)
3 + 4 (2 packages) Day 2 has more weight to be shipped than capacity of the ship. Try with a bigger capacity ship.
6 10 8 1 + 2 + 3
(3 packages)
4 (1 package) 8 kg capacity is valid but still try with a smaller capacity.
6 7 6 1 + 2 + 3
(3 packages)
4 (1 package) 6 kg capacity is valid but still try with a smaller capacity.

Since beg <= end becomes invalid, the search terminates. Thus we have 6 as the minimum capacity of the ship than can ship all the packages in 2 days.

Time complexity of the binary search algorithm : Log ( N )

Why is mid calculated as mid = beg + (end-beg)/2 ?


Program for finding the minimum capacity of a ship for shipping all the packages with given weights in N days

def CanShip (weights, max_capacity, days) :

    current_capacity = 0
    day_num = 1

    for w in weights :
        current_capacity += w

        # Current weight allotment exceeds the max_capacity, so this
        # weight may go on the ship the next day.
        if (current_capacity > max_capacity) :
            next_day_capacity = w

            # Check if this weight can never go on any ship
            # Return false and try with a bigger max_capacity
            if (next_day_capacity > max_capacity) :
                return False

            current_capacity = next_day_capacity
            day_num += 1

    # Perhaps more weights got shipped on previous days so return true and try
    # with a smaller max_capacity ship.
    if (day_num <= days) :
        return True

    return False

def FindCapacity (weights, days) :

    beg = 0
    end = 999999999 # Assume max capacity does not exceed this number.
    possible_capacity = -1

    if (len(weights) == 0) :
        return 0

    if (len(weights) == days) :
        return max(weights)

    while (beg <= end) :

        max_capacity = int(beg + (end-beg)/2)

        if (CanShip(weights, max_capacity, days)) :
            possible_capacity = max_capacity
            # Check if lesser capacity ship could be used than what has been found.
            end = max_capacity - 1
        else :
            beg = max_capacity + 1

    return possible_capacity

def main() :

    weights = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
    days = 5

    for days in range(1, 8) :
        print("Minimum capacity of ship for " + str(days) + " days : " + str(FindCapacity(weights, days)))

if __name__ == "__main__" :
   main()

Output

Minimum capacity of ship for 1 days : 55
Minimum capacity of ship for 2 days : 28
Minimum capacity of ship for 3 days : 21
Minimum capacity of ship for 4 days : 17
Minimum capacity of ship for 5 days : 15
Minimum capacity of ship for 6 days : 11
Minimum capacity of ship for 7 days : 10
#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>

using namespace std;

bool CanShip (vector<int>& weights, int max_capacity, int days) {

    int current_capacity = 0;
    int day_num = 1;

    for (const auto& w : weights) {
        current_capacity += w;

        /* Current weight allotment exceeds the max_capacity, so this
           weight may go on the ship the next day. */
        if (current_capacity > max_capacity) {
            int next_day_capacity = w;

            /* Check if this weight can never go on any ship */
            /* Return false and try with a bigger max_capacity */
            if (next_day_capacity > max_capacity)
                return false;

            current_capacity = next_day_capacity;
            day_num++;
        }
    }

    // Perhaps more weights got shipped on previous days so return true and try
    // with a smaller max_capacity ship.
    if (day_num <= days)
        return true;
    return false;
}

int FindCapacity (vector<int>& weights, int days) {

    int beg = 0;
    int end = INT_MAX;
    int possible_capacity = -1;

    if (weights.size() == 0)
        return 0;

    if (weights.size() == days)
        return *max_element(weights.begin(), weights.end());

    while (beg <= end) {

        int max_capacity = beg + (end-beg)/2;

        if (CanShip(weights, max_capacity, days)) {
            possible_capacity = max_capacity;
            // Check if lesser capacity ship could be used than what has been found.
            end = max_capacity - 1;
        } else {
            beg = max_capacity + 1;
        }
    }
    return possible_capacity;
}

int main() {

    vector<int> weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int days = 5;

    for (int days=1; days<=5; days+=2) {
        cout << "Minimum capacity of ship for " << days << " days : " << FindCapacity(weights, days) << endl;
    }
    return 0;
}

Output

Minimum capacity of ship for 1 days : 55
Minimum capacity of ship for 3 days : 21
Minimum capacity of ship for 5 days : 15
import java.util.Collections;
import java.util.List;
import java.util.Arrays;

class ShipPackages {

    boolean CanShip (List<Integer> weights, int max_capacity, int days) {

        int current_capacity = 0;
        int day_num = 1;

        for (int w : weights) {
            current_capacity += w;

            /* Current weight allotment exceeds the max_capacity, so this
               weight may go on the ship the next day. */
            if (current_capacity > max_capacity) {
                int next_day_capacity = w;

                /* Check if this weight can never go on any ship */
                /* Return false and try with a bigger max_capacity */
                if (next_day_capacity > max_capacity)
                    return false;

                current_capacity = next_day_capacity;
                day_num++;
            }
        }

        // Perhaps more weights got shipped on previous days so return true and try
        // with a smaller max_capacity ship.
        if (day_num <= days)
            return true;
        return false;
    }

    int FindCapacity (List<Integer> weights, int days) {

        int beg = 0;
        int end = Integer.MAX_VALUE;
        int possible_capacity = -1;

        if (weights.size() == 0)
            return 0;

        if (weights.size() == days)
            return Collections.max(weights);

        while (beg <= end) {

            int max_capacity = beg + ( end - beg ) / 2;

            if (CanShip(weights, max_capacity, days)) {
                possible_capacity = max_capacity;
                // Check if we can ship weights with lesser capacity than
                // what has been found.
                end = max_capacity - 1;
            } else {
                beg = max_capacity + 1;
            }
        }
        return possible_capacity;
    }

    public static void main (String[] args) {

        List<Integer> weights = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

        ShipPackages sp = new ShipPackages();

        for (int days = 1; days <= 5; days++) {
            System.out.println("Minimum capacity needed to ship within " + days + " day(s) is : " + sp.FindCapacity(weights, days));
        }
    }
}

Output

Minimum capacity needed to ship within 1 day(s) is : 55
Minimum capacity needed to ship within 2 day(s) is : 28
Minimum capacity needed to ship within 3 day(s) is : 21
Minimum capacity needed to ship within 4 day(s) is : 17
Minimum capacity needed to ship within 5 day(s) is : 15


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.