Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Solution of the problem
3.
Algorithm for the solution
4.
Implementation of the solution
4.1.
Complexity Analysis
5.
Frequently Asked Questions
6.
Key takeaways
Last Updated: Mar 27, 2024

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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will discuss the solution to a programming 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. Also, the ship takes only one turn between the ports in a day. And the packages are transferred to the ship by a conveyor. Thus we can only pick the packages in the order they appear. 

Let's see an example to develop a better understanding of the problem. Let's suppose we have seven items of weights 3 4 3 2 7 6 5, and we need to transfer them from one port to another within three days. The minimum capacity in the case of this example will be 11, as we can ship the packages in the following order-

{(3, 4 3),(2,7),(6,5)}

Recommended topic about, kth largest element in an array, and Euclid GCD Algorithm

Solution of the problem

To solve this problem, we will use a method that finds a suitable interval in which we can find the minimum capacity of the ship. And then, we search the whole interval to find the minimum value of capacity for which we can ship the packages in d days. 

To find the suitable interval for the minimum capacity of the ship, we need to draw some conclusions from the problem statement-

  • The minimum capacity of the ship will always be greater than or equal to the weight of the heaviest object.
  • The minimum capacity of the ship will always be lesser or equal to the total sum of the weight of the packages.

 

So, for any problem instance, the range of values we need to search for the minimum capacity will be - [weight on the heaviest object, the total weight of all the packages ]. And for searching the value, we can use binary search instead of linear search, which will help us optimize the process. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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.

Previous article
Longest Substring with At Least K Repeating Characters
Next article
Median of Two Sorted Arrays
Live masterclass