# 0-1 Knapsack Problem

Dynamic Programming

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 algorithm 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 i 1 2 3 4 value val 100 20 60 40 weight wt 3 2 4 1

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.

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT

ADVERTISEMENT