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

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 ?

**C++ Program for shipping all the packages with given weights in N days**

```
#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 ShipWithinDays (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;
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;
cout << "Minimum capacity of ship for " << days << " days : " << ShipWithinDays(weights, days) << endl;
days = 1;
cout << "Minimum capacity of ship for " << days << " days : " << ShipWithinDays(weights, days) << endl;
days = 2;
cout << "Minimum capacity of ship for " << days << " days : " << ShipWithinDays(weights, days) << endl;
return 0;
}
```

Output

```
Minimum capacity of ship for 5 days : 15
Minimum capacity of ship for 1 days : 55
Minimum capacity of ship for 2 days : 28
```

All rights reserved.