0-1 Knapsack Problem

Dynamic Programming

Share

In this tutorial we will be learning about 0-1 Knapsack problem. In this dynamic programming problem we have n items each with an associated weight and value (benefit or profit). The objective is to fill the knapsack with items such that we have a maximum profit without crossing the weight limit of the knapsack. Since this is a 0-1 knapsack problem hence we can either take an entire item or reject it completely. We can not break an item and fill the knapsack.

Point to remember

  • In this problem we have a Knapsack that has a weight limit W.
  • There are items i1, i2, ..., in each having weight w1, w2, … wn and some benefit (value or profit) associated with it v1, v2, ... vn
  • Our objective is to maximise the benefit such that the total weight inside the knapsack is at most W.
  • Since this is a 0-1 Knapsack problem so we can either take an entire item or reject it completely. We can not break an item and fill the knapsack.

Problem

Assume that we have a knapsack with max weight capacity W = 5
Our objective is to fill the knapsack with items such that the benefit (value or profit) is maximum.

Following table contains the items along with their value and weight.

item i1234
value val100206040
weight wt3241

Total items n = 4
Total capacity of the knapsack W = 5

Now we create a value table V[i,w] where, i denotes number of items and w denotes the weight of the items.
Rows denote the items and columns denote the weight.
As there are 4 items so, we have 5 rows from 0 to 4.
And the weight limit of the knapsack is W = 5 so, we have 6 columns from 0 to 5

V[i,w] w = 0 1 2 3 4 5
i = 0            
1            
2            
3            
4            

We fill the first row i = 0 with 0. This means when 0 item is considered weight is 0.

Then we fill the first column w = 0 with 0. This means when weight is 0 then items considered is 0.

Rule to fill the V[i,w] table.


if wt[i] > w then
V[i,w] = V[i-1,w]

else if wt[i] <= w then
V[i,w] = max( V[i-1,w], val[i] + V[i-1, w - wt[i]] )

After calculation, the value table V

V[i,w] w = 0 1 2 3 4 5
i = 0 0 0 0 0 0 0
1 0 0 0 100 100 100
2 0 0 20 100 100 120
3 0 0 20 100 100 120
4 0 40 40 100 140 140

Maximum value earned
Max Value = V[n,W]
= V[4,5]
= 140


Items that were put inside the knapsack
are found using the following rule

set i = n and w = W

while i and w > 0 do
  if V[i,w] != V[i-1,w] then
    mark the ith item
    set w = w - wt[i]
    set i = i - 1
  else
    set i = i - 1
  endif
endwhile

So, items we are putting inside the knapsack are 4 and 1.

C Code


#include<stdio.h>

void knapSack(int W, int n, int val[], int wt[]);
int getMax(int x, int y);

int main(void) {

	//the first element is set to -1 as
	//we are storing item from index 1
	//in val[] and wt[] array
	int val[] = {-1, 100, 20, 60, 40};	//value of the items
	int wt[] = {-1, 3, 2, 4, 1};		//weight of the items
	
	int n = 4;	//total items
	int W = 5;	//capacity of knapsack
	
	knapSack(W, n, val, wt);

	return 0;
}

int getMax(int x, int y) {
	if(x > y) {
		return x;
	} else {
		return y;
	}
}

void knapSack(int W, int n, int val[], int wt[]) {
	int i, w;

	//value table having n+1 rows and W+1 columns
	int V[n+1][W+1];

	//fill the row i=0 with value 0
	for(w = 0; w <= W; w++) {
		V[0][w] = 0;
	}

	//fille the column w=0 with value 0
	for(i = 0; i <= n; i++) {
		V[i][0] = 0;
	}

	//fill the value table
	for(i = 1; i <= n; i++) {
		for(w = 1; w <= W; w++) {
			if(wt[i] <= w) {
				V[i][w] = getMax(V[i-1][w], val[i] + V[i-1][w - wt[i]]);
			} else {
				V[i][w] = V[i-1][w];
			}
		}
	}

	//max value that can be put inside the knapsack
	printf("Max Value: %d\n", V[n][W]);
}

Time complexity

Time complexity of 0-1 Knapsack problem is O(nW) where, n is the number of items and W is the capacity of knapsack.