Capacity to ship packages within given days

 Today, let’s focus on a very good application of the famous algorithm binary search. Most of you may be familiar with binary search since it is widely used to implement different algorithms. In fact, I have used it in a few articles before. 

Minimum capacity to ship within given days - Problem statement

A conveyor belt has packages that must be shipped from one port to another within $d$ days.

The $i^{th}$ package on the conveyor belt has a weight of $w[i]$. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within $d$ days. Also note that we are not allowed to split the items apart and then ship.

Minimum capacity to ship within given days - Definition

We first need to define the window of possible capacities. Let $w$ be the weight array of items, $d$ be the number of days and $n$ be the number of items to be shipped. Let $W$ be the sum of the weights $w_i$ of all the items. Thus,

$$W = \sum_{i=1}^n w_i$$

Let $w_{max}$ be the maximum weight element in our array $w$. Then, the minimum possible capacity can be defined by the equation $C_{min-possible} = max(w_{max}, \lceil W/d \rceil)$. Not surprisingly, we can define the maximum possible capacity as $C_{max-possible} = \lceil n/d \rceil \cdot w_{max}$. 

Minimum capacity to ship within given days - Approach

With the above definitions under our belt, we can now move on and start solving the problem at hand. Let’s do a binary search on our window of possible capacities, choosing a capacity and check whether that capacity allows us to ship the packages within the given number of days. If so, we consider the first half of the window, otherwise, we consider the second half of the window in the next step. At each step, we halve the window size, until it reaches 0, at which point the algorithm exits. 

Note that our window size is defined by, $window-size = h - l + 1 = 0$ and $h + 1 = l$ which implies $h \lt l$ and at that point our $while$ loop terminates. Here’s the pseudocode for the algorithm of finding the minimum capacity to ship the packages within $d$ days.

**Input:** Package weight array $w$ and number of days $d$     

**Output:** The least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within $d$ days.  

$SHIP-WITHIN-DAYS(w, d)$  

$\phantom{{}++{}}$ $n \gets w.length$  

$\phantom{{}++{}}$ $mw \gets 0$  

$\phantom{{}++{}}$ $s \gets 0$  

$\phantom{{}++{}}$ `for ` $i = 1$ to $n$  

$\phantom{{}++{}}$ $\phantom{{}++{}}$ $s \gets s + w[i]$  

$\phantom{{}++{}}$ $\phantom{{}++{}}$  $mw \gets max(mw, w[i])$  

$\phantom{{}++{}}$ $h \gets \lceil \frac{n}{d} \rceil \cdot mw$  

$\phantom{{}++{}}$ $l \gets max(mw, \lceil \frac{s}{d} \rceil)$  

$\phantom{{}++{}}$ $c \gets 0$  

$\phantom{{}++{}}$ `while` $l \le h$  

$\phantom{{}++{}}$ $\phantom{{}++{}}$ $m \gets \lfloor \frac{(l + h)} {2} \rfloor$  

$\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $POSSIBLE-CAPACITY(w, m, d)$  

$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $h \gets m - 1$  

$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $c \gets m$  

$\phantom{{}++{}}$ $\phantom{{}++{}}$ `else`  

$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $l \gets m + 1$  

$\phantom{{}++{}}$ `return` c

**Input:** Package weight array $w$, capacity being considered $c$ and the number of days $d$     

**Output:** true, if items can be shipped within $d$ days using the given capacity $c$, false otherwise.  

$POSSIBLE-CAPACITY(w, c, d)$  

$\phantom{{}++{}}$ $n \gets w.length$  

$\phantom{{}++{}}$ $s \gets 0$  

$\phantom{{}++{}}$ `for` $i = 1$ to $n$  

$\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $s + w[i] \gt c$    

$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $d = d - 1$    

$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $s \gets w[i]$  

$\phantom{{}++{}}$ $\phantom{{}++{}}$ `else`  

$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $s \gets s + w[i]$  

$\phantom{{}++{}}$ $d \gets d - 1$  

$\phantom{{}++{}}$ $d \ge 0$

Here’s the sample implementation of algorithms described above along with a driver program.

	class ShipPackages {
	ShipPackages() {
	throw new AssertionError();
	}
	public static void main(String[] args) {
	final int[] w2 = { 3, 2, 2, 4, 1, 4 };
	final int d2 = 3;
	final int c = shipWithinDays(w2, d2);
	System.out.println(c);
	}
	static int shipWithinDays(int[] weights, int days) {
	final int n = weights.length;
	int mw = 0;
	int s = 0;
	for (int i = 0; i < n; i++) {
	s = s + weights[i];
	mw = Math.max(mw, weights[i]);
	}
	int h = (int) Math.ceil((double) n / days) * mw;
	int l = (int) Math.max(mw, Math.ceil((double) s / days));
	int c = 0;
	while (l <= h) {
	final int m = (l + h) / 2;
	if (possibleCap(weights, m, days)) {
	h = m - 1;
	c = m;
	} else
	l = m + 1;
	}
	return c;
	}
	static boolean possibleCap(int[] w, int c, int d) {
	final int n = w.length;
	int s = 0;
	for (int i = 0; i < n; i++) {
	if (s + w[i] > c) {
	d = d - 1;
	s = w[i];
	} else
	s = s + w[i];
	}
	d = d - 1;
	return d >= 0;
	}
	}

view raw ShipPackages.java hosted with ❤ by GitHub

Analysis

Let $m$ be the size of our capacity window and let $n$ be the length of the array $w$. We perform a binary search on our capacity window which incurs us $log_2 m$ steps. At each step, we call the procedure $POSSIBLE-CAPACITY$ which takes $O(n)$ time. So, our approach of finding the minimum capacity to ship the packages within $d$ days involves $O(log_2 m \cdot n)$ time complexity and $O(1)$ space.