0-1 knapsack problem using dynamic programming

0-1 Knapsack problem

0/1 Knapsack problem is a classic problem which is used to demonstrate application of greedy algorithm and dynamic programming. Greedy algorithm works for knapsack problem when partial weights are allowed but does not give optimal solution for 0/1 problem when partial weights are not allowed. In this post, as we are discussing 0/1 knapsack problem, we will focus on dynamic programming solution of it.

There are many flavors in which 0–1 Knapsack problem can be asked. Some are list below

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 combination of artifacts thief takes, so that he gets maximum value and weight of all artifacts taken by him is less the capacity of his bag. 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 stored, 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 a file. We cannot store partial file. Hence, this is a case of 0-1 knapsack problem.

0-1 Knapsack problem in mathematics terms:

There are N items <I1,I2,................In> each having a weight <w1,w2,...............wn>.
Each item has a value associated with it <v1,v2, ..........vn>
Given a limit W we have to find a subset of K items such that 
                  Sum (w1, w2..... wk) <= W  &
                  Sum (v1,v2,.........vk) is maximum.

Brute force method would try all subsets of set of items and see which one gives as the maximum value. This method would be of exponential order because there are 2^n subsets for a set with n elements.
Can we do better than this? For each item in set, 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 possibility is that item is not included into already optimal subset. In this case, 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. So problem still remains with weight W and Value V but with N-1 items to be considered.
Inclusion or exclusion of an item depends on two conditions :

1. Weight of the item is less than the total weight, then can be included. If it weight is more than total weight, directly exclude it. 
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.

0-1 knapsack problem: Dynamic programming Implementation

Going 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 jth item was included.

#include <stdio.h>
 
int knapsack01(int w[], int v[], int N, int W){
 
  int table[N+1][W+1];
  int i, j;
 
  for(i=0;i<=N; i++){
     for(j=0; j<=W; j++){
        table[i][j]=0;
     }
  }
 
  for(i=0; i<=N; i++){
     for(j=0; j<=W; j++){
         if(i == 0 || j == 0){
            table[i][j] = 0;
         }
        /* Condition when item can be included
           We check if inclusion of this item leads to increase in 
           value.
           If without including this value, for this weight, value was 
           greater than including this item, then we would take previous
           value. */ 
        else if(w[i-1] <= j){
            table[i][j] = table[i-1][j] > (v[i-1] + \
              table[i-1][j-w[i-1]]) ? table[i-1][j] : \
                        v[i-1] + table[i-1][j-w[i-1]]; 
         }
         else{
              table[i][j] = table[i-1][j];
         }
 
       }
     }
     return table[N][W];   
}
int main(void) {
	int w[] = { 2,3,4,1,2 };
	int v[] = { 5,4,1,2,1 };
	int W = 10;
	int size = sizeof(w)/sizeof(w[0]);
	printf("Optimal Value : %d ", knapsack01(w, v, size, W));
	return 0;
}

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.

#include <stdio.h>
 
int minimumCoins(int denominations[], int C, int n){
	int i,j;
	#define MAX_COINS C
	int M[C];
	for(i=0;i<=C;i++){
		M[i] = MAX_COINS;
	}
	M[0]=0;
	M[1]=1;
 
	for(i=2;i<=C; i++){
	    for(j=0;j<n;j++){
		if((i-denominations[j]) >=0 && M[i-denominations[j]]+1 < M[i])
		     M[i] = M[i-denominations[j]] +1;
		}
	}
	return M[C];    
}
int main(void) {
	int denominations[] = {1,2,3,4};
	int C = 10;
	int size = sizeof(denominations)/sizeof(denominations[0]);
	printf("Minimum number of coins required : %d", 
                minimumCoins(denominations, C, size));
	return 0;
}

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.

http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf