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.

- 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.

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.

```
#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 of 0 1 Knapsack problem is O(nW) where, n is the number of items and W is the capacity of knapsack.

ADVERTISEMENT