How to find the minimum capacity of the ship to ship packages within d days.

Algorithm for the solution

1. Take an array of weights of packages and the number of days from the user as input.
2. Find the interval- [weight on the heaviest object, the total weight of all the packages ].
3. Apply binary search on this interval by dividing the interval [weight on the heaviest object, the total weight of all the packages ]  into half and assuming the capacity of the ship to be the middle element. Check if it is possible to ship the packages with the ship. If yes, we recursively call binary search for the subarray on the left of the middle element or the right subarray of the middle element.
4. Return the minimum capacityof the ship as answer.

Implementation of the solution

#include <bits/stdc++.h>
using namespace std;
//To check if it is possible to transfer the packages within d
//days with a given capacity or not.
bool validcapacity(vector<int> &weights, int noofobj, int d, int maxcap)
{
    //To keep track of the number of the days.
    int days = 1;
    int sumtillnow = 0;
    //Traverse through all the weights.
    for(int i=0;i<noofobj;i++)
    {
        sumtillnow += weights[i];
        //When the weight of packages becomes more than the capacity.
        if (sumtillnow > maxcap)
        {
            days++;
            sumtillnow=weights[i];
        }
        //If days required are more than d.
        if (days>d)
        {
            return false;
        }
    }
    //If all the packages can be shipped with the given capacity
    //within d days.
    return true;
}
//To find the total sum of packages.
int sumofobj(vector<int> &weights, int n)
{
    int sum = 0;
    for (int i=0;i<n;i++)
    {
        sum+=weights[i];
    }
    return sum;
}
//Function to find the minimum capacity of the ship.
int findmincap(vector<int> &weights, int n, int d)
{
    int totalsum = sumofobj(weights, n);
    int left = weights[0];
    //Finding the weight of the heaviest object.
    for(int i=1;i<n;i++)
    {
        left=max(left, weights[i]);
    }
    //Total sum of weights of the packages.
    int right=totalsum;
    int result=-1;
    //Binary search.
    while(left<=right)
    {
        int midelement=left+(right-left)/2;
        if(validcapacity(weights, n, d, midelement))
        {
            //If the middle element is a valid capacity for the
            //ship, search in the left subarray.
            result=midelement;
            right=midelement-1;
        }
        else
        {
            //Otherwise search in the right subarray.
            left=midelement+1;
        }
    }
    return result;
}
//Driver function.
int main()
{
    cout<<"Enter no. of packages and days- ";
    int noofobj, d;
    cin>>noofobj>>d;
    vector<int> weights;
    cout<<"Enter the weights of the packages ";
    for(int i=0;i<noofobj;i++)
    {
        int a;
        cin>>a;
        weights.push_back(a);
    }
    int mincap= findmincap(weights, noofobj, d);
    cout<<mincap;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input-

7 2
1 2 3 4 5 6 7

Output-

Enter no. of packages and days-
Enter the weights of the packages- 
15

Complexity Analysis

The time complexity of this approach is- O(N*log(length of search interval for capacity), as we are using binary search. 

The space complexity of this approach is O(1)

Frequently Asked Questions

1. What is the binary search?
   Binary search is a method used to search elements in a sorted array. In it, we half the array and compare the middle element with the key, and based on that, drop one half of the array and repeat the process for the other half until we find the element in the array.
    
2. Is binary search a divide and conquer method?
   No, the binary search is not a divide and conquer method. It is a decrease and conquers method.
    
3. Which search algorithm is better linear or binary?
   Binary search is better than linear search as it has lesser time complexity because it makes less number of comparisons.
    
4. What is the difference between linear and binary search?
   In linear search, we compare each element with the key one by one and return the index when we find the key, whereas in binary search, we half the array and compare the key with the middle element, and decide if the key will be in the right half subarray or left half subarray, we again search in the one half and abandon the other half.
    
5. What is the disadvantage of a binary search?
   Disadvantages of binary search are that it is recursive, thus requiring more space, and caching is poor in the case of binary search.

Key takeaways

In this blog, we learned about the solution of the problem in which we have to find the minimum capacity of the ship to ship packages within d days. We are already given the weight of the packages. We need to find the minimum capacity of the ship.

We started with drawing out some conclusions from the problem statement- that the ship's capacity will always be greater than or equal to the weight of the heaviest object, and it will always be less than or equal to the total sum of the weight of all the packages. Now we get an interval in which the minimum capacity of the shape will lie. Then, we use binary search over the interval to find the minimum capacity to transfer all the packages from one port to another within d days using a ship.

Check out this problem - Longest Subarray With Sum K 

You can read more about binary search and practice similar questions on code studio.