Problem Statement: You are the owner of a Shipment company. You use conveyor belts to ship packages from one port to another. The packages must be shipped within ‘d’ days.
The weights of the packages are given in an array ‘of weights’. The packages are loaded on the conveyor belts every day in the same order as they appear in the array. The loaded weights must not exceed the maximum weight capacity of the ship.
Find out the least-weight capacity so that you can ship all the packages within ‘d’ days.
Examples
Example 1:
Input Format: N = 5, weights[] = {5,4,5,2,3,4,5,6}, d = 5
Result: 9
Explanation: If the ship capacity is 9, the shipment will be done in the following manner:
Day Weights Total
1 - 5, 4 - 9
2 - 5, 2 - 7
3 - 3, 4 - 7
4 - 5 - 5
5 - 6 - 6
So, the least capacity should be 9.
Example 2:
Input Format: N = 10, weights[] = {1,2,3,4,5,6,7,8,9,10}, d = 1
Result: 55
Explanation: We have to ship all the goods in a single day. So, the weight capacity should be the summation of all the weights i.e. 55.
Observation:
- Minimum ship capacity: The minimum ship capacity should be the maximum value in the given array. Let’s understand using an example. Assume the given weights array is {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and the ship capacity is 8. Now in the question, it is clearly stated that the loaded weights in the ship must not exceed the maximum weight capacity of the ship. For this constraint, we can never ship the weights 9 and 10, if the ship capacity is 8. That is why, in order to ship all the weights, the minimum ship capacity should be equal to the maximum of the weights array i.e. nax(weights[]).
- Maximum capacity: If the ship capacity is equal to the sum of all the weights, we can ship all goods within a single day. Any capacity greater than this will yield the same result. So, the maximum capacity will be the summation of all the weights i.e. sum(weights[]).
From the observations, it is clear that our answer lies in the range
[max(weights[]), sum(weights[])].
How to calculate the number of days required to ship all the weights for a certain ship capacity:
In order to calculate this, we will write a function findDays(). This function accepts the weights array and a capacity as parameters and returns the number of days required for that particular capacity. The steps will be the following:
findDays(weights[], cap):
- We will declare to variables i.e. ‘days’(representing the required days) and ‘load’ (representing the loaded weights in the ship). As we are on the first day, ‘days’ should be initialized with 1 and ‘load’ should be initialized with 0.
- Next, we will use a loop(say i) to iterate over the weights. For each weight, weights[i], we will check the following:
- If load+weights[i] > cap: If upon adding current weight with load exceeds the ship capacity, we will move on to the next day(i.e. day = day+1) and then load the current weight(i.e. Set load to weights[i], load = weights[i]).
- Otherwise, We will just add the current weight to the load(i.e. load = load+weights[i]).
- Finally, we will return ‘days’ which represents the number of days required.
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Brute Force Approach
Algorithm / Intuition
Naive Approach:
The extremely naive approach is to check all possible capacities from max(weights[]) to sum(weights[]). The minimum number for which the required days <= d value, will be our answer.
Algorithm:
- We will use a loop(say cap) to check all possible capacities.
- Next, inside the loop, we will send each capacity to the findDays() function to get the number of days required for that particular capacity.
- The minimum number, for which the number of days <= d, will be the answer.
Dry-run: Please refer to the video for the dry-run.
Code
#include <bits/stdc++.h>
using namespace std;
int findDays(vector<int> &weights, int cap) {
int days = 1; //First day.
int load = 0;
int n = weights.size(); //size of array.
for (int i = 0; i < n; i++) {
if (load + weights[i] > cap) {
days += 1; //move to next day
load = weights[i]; //load the weight.
}
else {
//load the weight on the same day.
load += weights[i];
}
}
return days;
}
int leastWeightCapacity(vector<int> &weights, int d) {
//Find the maximum and the summation:
int maxi = *max_element(weights.begin(), weights.end());
int sum = accumulate(weights.begin(), weights.end(), 0);
for (int i = maxi; i <= sum; i++) {
if (findDays(weights, i) <= d) {
return i;
}
}
//dummy return statement:
return -1;
}
int main()
{
vector<int> weights = {5, 4, 5, 2, 3, 4, 5, 6};
int d = 5;
int ans = leastWeightCapacity(weights, d);
cout << "The minimum capacity should be: " << ans << "\n";
return 0;
}
import java.util.*;
public class tUf {
public static int findDays(int[] weights, int cap) {
int days = 1; //First day.
int load = 0;
int n = weights.length; //size of array.
for (int i = 0; i < n; i++) {
if (load + weights[i] > cap) {
days += 1; //move to next day
load = weights[i]; //load the weight.
} else {
//load the weight on the same day.
load += weights[i];
}
}
return days;
}
public static int leastWeightCapacity(int[] weights, int d) {
//Find the maximum and the summation:
int maxi = Integer.MIN_VALUE, sum = 0;
for (int i = 0; i < weights.length; i++) {
sum += weights[i];
maxi = Math.max(maxi, weights[i]);
}
for (int i = maxi; i <= sum; i++) {
if (findDays(weights, i) <= d) {
return i;
}
}
//dummy return statement:
return -1;
}
public static void main(String[] args) {
int[] weights = {5, 4, 5, 2, 3, 4, 5, 6};
int d = 5;
int ans = leastWeightCapacity(weights, d);
System.out.println("The minimum capacity should be: " + ans);
}
}
from typing import List
def findDays(weights: List[int], cap: int) -> int:
days = 1 # First day
load = 0
n = len(weights) # size of array
for i in range(n):
if load + weights[i] > cap:
days += 1 # move to next day
load = weights[i] # load the weight
else:
# load the weight on the same day
load += weights[i]
return days
def leastWeightCapacity(weights: List[int], d: int) -> int:
# Find the maximum and the summation
maxi = max(weights)
summation = sum(weights)
for i in range(maxi, summation + 1):
if findDays(weights, i) <= d:
return i
# dummy return statement
return -1
weights = [5, 4, 5, 2, 3, 4, 5, 6]
d = 5
ans = leastWeightCapacity(weights, d)
print("The minimum capacity should be:", ans)
function findDays(weights, cap) {
let days = 1; // First day.
let load = 0;
let n = weights.length; // Size of array.
for (let i = 0; i < n; i++) {
if (load + weights[i] > cap) {
days += 1; // Move to next day.
load = weights[i]; // Load the weight.
} else {
// Load the weight on the same day.
load += weights[i];
}
}
return days;
}
function leastWeightCapacity(weights, d) {
// Find the maximum and the summation:
let maxi = Math.max(...weights);
let sum = weights.reduce((acc, weight) => acc + weight, 0);
for (let i = maxi; i <= sum; i++) {
if (findDays(weights, i) <= d) {
return i;
}
}
// Dummy return statement:
return -1;
}
let weights = [5, 4, 5, 2, 3, 4, 5, 6];
let d = 5;
let ans = leastWeightCapacity(weights, d);
console.log("The minimum capacity should be: " + ans);
Output:The minimum capacity should be: 9.
Complexity Analysis
Time Complexity: O(N * (sum(weights[]) – max(weights[]) + 1)), where sum(weights[]) = summation of all the weights, max(weights[]) = maximum of all the weights, N = size of the weights array.
Reason: We are using a loop from max(weights[]) to sum(weights[]) to check all possible weights. Inside the loop, we are calling findDays() function for each weight. Now, inside the findDays() function, we are using a loop that runs for N times.
Space Complexity: O(1) as we are not using any extra space to solve this problem.
Optimal Approach
Algorithm / Intuition
Optimal Approach(Using Binary Search):
We are going to use the Binary Search algorithm to optimize the approach.
The primary objective of the Binary Search algorithm is to efficiently determine the appropriate half to eliminate, thereby reducing the search space by half. It does this by determining a specific condition that ensures that the target is not present in that half.
Now, we are not given any sorted array on which we can apply binary search. Upon closer observation, we can recognize that our answer space, represented as [max(weights[]), sum(weights[])], is actually sorted. Additionally, we can identify a pattern that allows us to divide this space into two halves: one consisting of potential answers and the other of non-viable options. So, we will apply binary search on the answer space.
Algorithm:
- First, we will find the maximum element i.e. max(weights[]), and the summation i.e. sum(weights[]) of the given array.
- Place the 2 pointers i.e. low and high: Initially, we will place the pointers. The pointer low will point to max(weights[]) and the high will point to sum(weights[]).
- Calculate the ‘mid’: Now, inside the loop, we will calculate the value of ‘mid’ using the following formula:
mid = (low+high) // 2 ( ‘//’ refers to integer division) - Eliminate the halves based on the number of days required for the capacity ‘mid’:
We will pass the potential capacity, represented by the variable ‘mid’, to the ‘findDays()‘ function. This function will return the number of days required to ship all the weights for the particular capacity, ‘mid’.- If munerOfDays <= d: On satisfying this condition, we can conclude that the number ‘mid’ is one of our possible answers. But we want the minimum number. So, we will eliminate the right half and consider the left half(i.e. high = mid-1).
- Otherwise, the value mid is smaller than the number we want. This means the numbers greater than ‘mid’ should be considered and the right half of ‘mid’ consists of such numbers. So, we will eliminate the left half and consider the right half(i.e. low = mid+1).
- Finally, outside the loop, we will return the value of low as the pointer will be pointing to the answer.
The steps from 3-4 will be inside a loop and the loop will continue until low crosses high.
Note: Please make sure to refer to the video and try out some test cases of your own to understand, how the pointer ‘low’ will be always pointing to the answer in this case. This is also the reason we have not used any extra variable here to store the answer.
Dry-run: Please refer to the video for the dry-run.
Code
#include <bits/stdc++.h>
using namespace std;
int findDays(vector<int> &weights, int cap) {
int days = 1; //First day.
int load = 0;
int n = weights.size(); //size of array.
for (int i = 0; i < n; i++) {
if (load + weights[i] > cap) {
days += 1; //move to next day
load = weights[i]; //load the weight.
}
else {
//load the weight on the same day.
load += weights[i];
}
}
return days;
}
int leastWeightCapacity(vector<int> &weights, int d) {
//Find the maximum and the summation:
int low = *max_element(weights.begin(), weights.end());
int high = accumulate(weights.begin(), weights.end(), 0);
while (low <= high) {
int mid = (low + high) / 2;
int numberOfDays = findDays(weights, mid);
if (numberOfDays <= d) {
//eliminate right half
high = mid - 1;
}
else {
//eliminate left half
low = mid + 1;
}
}
return low;
}
int main()
{
vector<int> weights = {5, 4, 5, 2, 3, 4, 5, 6};
int d = 5;
int ans = leastWeightCapacity(weights, d);
cout << "The minimum capacity should be: " << ans << "\n";
return 0;
}
import java.util.*;
public class tUf {
public static int findDays(int[] weights, int cap) {
int days = 1; //First day.
int load = 0;
int n = weights.length; //size of array.
for (int i = 0; i < n; i++) {
if (load + weights[i] > cap) {
days += 1; //move to next day
load = weights[i]; //load the weight.
} else {
//load the weight on the same day.
load += weights[i];
}
}
return days;
}
public static int leastWeightCapacity(int[] weights, int d) {
//Find the maximum and the summation:
int low = Integer.MIN_VALUE, high = 0;
for (int i = 0; i < weights.length; i++) {
high += weights[i];
low = Math.max(low, weights[i]);
}
while (low <= high) {
int mid = (low + high) / 2;
int numberOfDays = findDays(weights, mid);
if (numberOfDays <= d) {
//eliminate right half
high = mid - 1;
} else {
//eliminate left half
low = mid + 1;
}
}
return low;
}
public static void main(String[] args) {
int[] weights = {5, 4, 5, 2, 3, 4, 5, 6};
int d = 5;
int ans = leastWeightCapacity(weights, d);
System.out.println("The minimum capacity should be: " + ans);
}
}
def findDays(weights, cap):
days = 1 # First day
load = 0
n = len(weights) # Size of array
for i in range(n):
if load + weights[i] > cap:
days += 1 # Move to next day
load = weights[i] # Load the weight
else:
# Load the weight on the same day
load += weights[i]
return days
def leastWeightCapacity(weights, d):
# Find the maximum and the summation
low = max(weights)
high = sum(weights)
while low <= high:
mid = (low + high) // 2
numberOfDays = findDays(weights, mid)
if numberOfDays <= d:
# Eliminate right half
high = mid - 1
else:
# Eliminate left half
low = mid + 1
return low
weights = [5, 4, 5, 2, 3, 4, 5, 6]
d = 5
ans = leastWeightCapacity(weights, d)
print("The minimum capacity should be:", ans)
function findDays(weights, cap) {
let days = 1; // First day.
let load = 0;
let n = weights.length; // size of array.
for (let i = 0; i < n; i++) {
if (load + weights[i] > cap) {
days += 1; // move to next day.
load = weights[i]; // load the weight.
} else {
// load the weight on the same day.
load += weights[i];
}
}
return days;
}
function leastWeightCapacity(weights, d) {
// Find the maximum and the summation:
let low = Math.max(...weights);
let high = weights.reduce((sum, weight) => sum + weight, 0);
while (low <= high) {
let mid = Math.floor((low + high) / 2);
let numberOfDays = findDays(weights, mid);
if (numberOfDays <= d) {
// eliminate right half.
high = mid - 1;
} else {
// eliminate left half.
low = mid + 1;
}
}
return low;
}
let weights = [5, 4, 5, 2, 3, 4, 5, 6];
let d = 5;
let ans = leastWeightCapacity(weights, d);
console.log("The minimum capacity should be:", ans);
Output:The minimum capacity should be: 9.
Complexity Analysis
Time Complexity: O(N * log(sum(weights[]) – max(weights[]) + 1)), where sum(weights[]) = summation of all the weights, max(weights[]) = maximum of all the weights, N = size of the weights array.
Reason: We are applying binary search on the range [max(weights[]), sum(weights[])]. For every possible answer ‘mid’, we are calling findDays() function. Now, inside the findDays() function, we are using a loop that runs for N times.
Space Complexity: O(1) as we are not using any extra space to solve this problem.
Video Explanation
Special thanks to KRITIDIPTA GHOSH for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article