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.


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. 

Comments

Post a Comment

Popular posts from this blog

Introducing Java Reactive Extentions in to a SpringBoot Micro Service

Image
Introduction Today we are going to take a look at Reactive Programming using Java8 and RxJava, which is a library for composing asynchronous and event-based programs by using observable sequences. RxJava stands for Reactive Extensions for the JVM. It extends the observer pattern [Gamma95] to support sequences of data/events and adds operators that allow you to compose sequences together declaratively while abstracting away concerns about things like low-level threading, synchronization, thread-safety and concurrent data structures [1]. Pre-Requisites : Having a good knowledge about Java8, Functional Programming and spring boot microservices. What is Reactive programming? In essence, Reactive programming is an asynchronous programming paradigm concerned with data streams. The system time, a list of entries from the DB/API, user clicks, everything can be a stream of data. Data from different streams can easily be combined and transformed, and in the end processed/observed by the
Read more

Optimal binary search trees

Image
Suppose that we are designing a program to translate text from English to French. For each occurrence of each English word in the text, we need to look up its French equivalent. We could perform these lookup operations by building a binary search tree with $n$ English words as keys and their French equivalents as satellite data. Because we will search the tree for each individual word in the text, we want the total time spent searching to be as low as possible. We could ensure an $Θ(log_2 \;n)$ search time per occurrence by using a red-black tree or any other balanced binary search tree. Words appear with different frequencies, however, and a frequently used word such as the may appear far from the root while a rarely used word appears near the root. Such an organization would slow down the translation, since the number of nodes visited when searching for a key in a binary search tree equals one plus the depth of the node containing the key. We want words that occur frequently in the t
Read more

Edit distance

Image
Biological applications often need to compare the DNA of two (or more) different organisms. A strand of DNA consists of a string of molecules called bases, where the possible bases are adenine, guanine, cytosine, and thymine. Representing each of these bases by its initial letter, we can express a strand of DNA as a string over the finite set $\{A, C, G, T\}$. For example, the DNA of one organism may be $S1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA$, and the DNA of another organism may be $S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA$. One reason to compare two strands of DNA is to determine how “similar” the two strands are, as some measure of how closely related the two organisms are. We can, and do, define similarity in many different ways. For example, we can say that two strands are similar if the number of changes needed to turn one into the other is small. [1] We formalize this notion of similarity in our Edit distance problem. 15-5 Edit distance - Problem Statement In order to transform one sour
Read more