0-1 knapsack problem

Problem Statement

The 0-1 knapsack problem is the following. A thief robbing a store finds n items. The $i$ th item is worth $v_i$ dollars and weighs $w_i$ pounds, where $v_i$ and $w_i$ are integers. The thief wants to take as valuable a load as possible, but he can carry at most $W$ pounds in his knapsack, for some integer $W$. Which items should he take? We call this the 0-1 knapsack problem because for each item, the thief must either take it or leave it behind; he cannot take a fractional amount of an item or take an item more than once. [1]

Now let’s take an exercise from our CLRS book [1].

Exercise 16.2-2 

Give a dynamic programming solution to the 0-1 knapsack problem that runs in $O(n \cdot W)$ time, where $n$ is the number of items and $W$ is the maximum weight of items that the thief can put in his knapsack. [1]

0-1 knapsack - Definition 

Let $n$ be the number of items, $W$ be the capacity of the knapsack. Let $i$ be the current item being considered, $v_i$ and $w_i$ be it’s value and weight respectively. Let $k[1 \ldots n][1 \ldots w]$ be a table holding optimal solutions to subproblems. Let $j$ be the size of the subproblem. We can write our recurrence to the 0-1 knapsack problem as follows:

$$k[i][j] =
\begin{cases}
max(v_i + k[i - 1][j - w_i], \;k[i-1][j]),  & \text{if $w_i \le j$} \\[2ex]
k[i-1][j], & \text{otherwise.}
\end{cases}$$

0-1 knapsack - Approach

If the $w_i \le j$, then we can put this item and take an optimal worth that we can achieve with the remaining capacity without including this item again. We also can exclude the item in the first place, and calculate the maximum worth that we can obtain with the given capacity. The maximum value of those two would be the optimal worth which we can achieve. Otherwise, we just calculate the maximal worth that we can obtain without including the $i^{th}$ item, since the $i^{th}$ item is heavier than the capacity $j$. Here’s the algorithm for finding maximum worth.

**Input:** value and weight arrays $v$, $w$ and $c-$ the capacity of the knapsack  
**Output:** Table $k$ which contains the maximum attainable worth  
$0-1KNAPSACK(v, w, c)$              
$\phantom{{}++{}}$ $n \gets v.length$  
$\phantom{{}++{}}$ let $k[1 \ldots n + 1][1 \ldots c + 1]$ be a new table  
$\phantom{{}++{}}$ `for` $i = 1$ to $n + 1$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ $k[i][1] \gets 0$  
$\phantom{{}++{}}$ `for` $j = 2$ to $c + 1$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ $k[1][j] \gets 0$  
$\phantom{{}++{}}$ `for` $i = 2$ to $n + 1$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ `for` $j = 2$ to $c + 1$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ `if` $w[i - 1] \le j$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $k[i][j] \gets max(v[i - 1] + k[i - 1][j - w[i - 1]], \;k[i - 1][j])$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ `else`  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $k[i][j] \gets k[i - 1][j]$  
$\phantom{{}++{}}$ return $k$

 

Figure 1 shows the table $k$ computed by the procedure $0-1KNAPSACK$ on the two input arrays $v = $[ 20, 5, 10, 40, 15, 25 ] and $w = $[ 1, 2, 3, 8, 7, 4 ] for a knapsack with capacity $c = 10$. 

$$\begin{array}{|c|c|c|}  \hline
 & \text{1}  & \text{2} & \text{3} & \text{4} & \text{5} & \text{6}& \text{7}& \text{8} & \text{9} & \text{10} & \text{11} \\ \hline
\text{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
\text{2} & 0 & 20 & 20 & 20 & 20 & 20 & 20 & 20 & 20 & 20 & 20 \\ \hline
\text{3} & 0 & 20 & 20 & 25 & 25 & 25 & 25 & 25 & 25 & 25 & 25 \\ \hline
\text{4} & 0 & 20 & 20 & 25 & 30 & 30 & 35 & 35 & 35 & 35 & 35 \\ \hline
\text{5} & 0 & 20 & 20 & 25 & 30 & 30 & 35 & 35 & 40 & 60 & 60 \\ \hline
\text{6} & 0 & 20 & 20 & 25 & 30 & 30 & 35 & 35 & 40 & 60 & 60 \\ \hline
\text{7} & 0 & 20 & 20 & 25 & 30 & 45 & 45 & 50 & 55 & 60 & 60 \\ \hline
\end{array}$$

Finding items in our knapsack

Now, we need to find the items that should be there in the knapsack from the table computed at step one. Here’s the algorithm for finding items in an optimal solution.

**Input:** Table $k$ computed at previous step and $w-$ the weight array  
**Output:** Items that should be in the knapsack in order to get the maximal worth  
$FIND-ITEMS(k, w)$  
$\phantom{{}++{}}$ $j \gets k[1].length$  
$\phantom{{}++{}}$ $n \gets k.length$  
$\phantom{{}++{}}$ `for` $i = n$ down to $2$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $k[i - 1][j] \lt k[i][j]$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ print $i - 1$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $j \gets j - w[i - 1]$ 

We start from the bottom right position of the table $k$, tracing back all the way up until we reach the top row. At each step, we check whether the current cell is larger than the cell which lies above it. If so, we take the current item, deduct it's weight from the remaining capacity and move on to the next step.
Our approach of finding items in an optimal solution involves, $O(n)$ time and $O(1)$ space complexity.

Sample Implementation

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

Analysis

Our approach of finding the most valuable load for a given knapsack capacity takes $O(\mathrm{n}^2)$ space and time complexity.

References

[1] https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844

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