**Given** :

N number of packages 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.

**Objective** : 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).

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
```

All rights reserved.