# 0-1 Knapsack problem

0/1 Knapsack is typical problem which is used to demonstrate application of greedy algorithm as well as dynamic programming. There are cases when applying greedy algorithm does not give optimal solution.

There are many flavors in which *Knapsack problem* can be asked.

1. A thief enters a museum and want to steal artifacts from there. Every artifact has a weight and value associated with it. Thief carries a knapsack (bag) which can take only a specific weight.

Problem is to find the combination of artifacts thief takes so that he gets maximum value and weight of all the taken artifacts is less the capacity of the bag he has brought.

Thief cannot take any artifact partially. Either he takes it or leaves it. Hence the problem is 0-1 knapsack.

2. Second flavor is : We have N files each having a size say Si. We have a total storage capacity of W bytes. For each file to be store the re-computation cost is Vi. Problem is to store as files on storage that combined size of all files is less than W and their re-computation value is maximum.

We can either store or leave the file. We cannot store partial file. Hence this is a case of __0-1 knapsack problem.__

__Knapsack problem in pure mathematics terms:__

### Analysis

Brute force method would try all the subsets of the set of items and see which one gives as the maximum value. This method would be of exponential order.

Can we do better? If we consider every item, there are two possibilities associated with it.

First, **given item is included in the subset which is optimal.** Then we need to find out all the items in remaining N-1 items which can **optimize the sub problem** for weight W-wk. Value of this item is added to candidate maximum value.

Second case is the **item is not included** into the set. In that case, we need to find out items in remaining N-1 items which can **optimize the the original problem**. Value of this item is not added into candidate maximum value. Inclusion depends on two conditions : 1. Weight of the item is less than the total weight. 2. Inclusion of item increases the value which was already there with K-1 items with W-Wk weight.

When remaining allowed weight is zero (case 1 ) or we have considered all items (case 2) , we have reached the solution.

## Dynamic programming Implementation of knapsack problem

In implementation, we define a two dimensional array of size N * W.

Element in this array can be interpreted as for a given value of W *w (w<W)* and for a given number of items *i (i < N)*, best solution would be value of that element i.e *array(I, w)*.

For i =0 and w=0, all the values will be zero. Hence first column and first row will be filled with all zero values. We would build on top of that.

For each item in set, we would check for maximum value we can get for weight w.

As explained in the analysis, based on its two conditions, we include or exclude the item.

We can easily keep track of which items are included in optimal structure by keeping boolean two dimensional array. Each element a[i,j] is true if for weight* j ith* item was included.

### Code

One similar problem which can be solved with same approach is minimum number of coins to be used to get change of a particular amount.

I am skipping the whole analysis and directly pasting the code here.

### Complexity analysis

Complexity of the dynamic programming implementation of *knapsack problem* is **O(N *W)**. Space complexity is again **O(N*W)**. It is thumb rule that we trade space for time in dynamic programming.

### Reference