In my last post on dynamic programming, we learnt about integer knapsack problem. Today we will see what if it is forbidden to use more than one instance of each type of item.**Question:** You have n types of items, where the i^{th} item type has an integer size s_{i} and a real value v_{i}. You need to ﬁll a knapsack of total capacity C with a selection of items of maximum value.**Answer:** Let M(i , j) denote the optimal value filling exactly a size j knapsack using a subset of items 1...i. Where i varies from 1…n and j varies from 1…C. Lets see if we can compute a recursive formula for calculating M(i , j).

There are 2 possible solution for calculating M(i,j).

- If we don’t use i
^{th}item, then M(i , j) = M(i - 1 , j). - If we use i
^{th}then M(i , j) = M(i - 1 , j – s_{i}) + v_{i}

Our final value of M(i , j) will be the maximum of above 2:

M(i , j) = max{ M(i - 1 , j) , M(i - 1 , j – s

_{i}) + v_{i}}Also if s

_{i}> j ; the current object i exceeds the capacity, we definitely can not pick it. So M(i, j) = M(i − 1, j) for this case.

Finally M(i, j) will be defined as

0 if i = 0 or j = 0

M(i , j) = M(i-1, j) if s_{i}> j

max{ M(i - 1 , j) , M(i - 1 , j – s_{i}) + v_{i}} (otherwise)

Since M(i , j) denotes the optimal value filling exactly a size j knapsack using 1..i items. our answer for capacity C and item 1..n will be

Again as we have seen that at any point in time, we just need (i-1)

I am leaving the exercise of reconstructing, which all items to put in knapsack in order to achieve calculated optimal value, to readers.

Here is a well-explained video of solving of 0/1 knapsack problem with pen and paper.

**M[n][C]**.**Code:**

//0-1 knapsack problem

#include <iostream>

using namespace std;

#define MAX_ITEMS 10

#define MAX_CAPACITY 100

int knapsack(int value[], int weight[], int n, int C)

{

//For code simplicity, I'm creating a fixed size array.

//Actually it should depend on n and C

int M[MAX_ITEMS+1][MAX_CAPACITY+1] = {{0,},}; //initialize to zero

int i, j;

for(i=1; i<= n; i++)

{

for(j=1; j<=C; j++)

{

if(weight[i-1] > j)

M[i][j] = M[i-1][j];

else

{

M[i][j] = M[i-1][j];

if( (M[i-1][j-weight[i-1]]+value[i-1]) > M[i][j])

M[i][j] = M[i-1][j-weight[i-1]] + value[i-1];

}

}

}

return M[n][C];

}

//This main function is here just to show how to call knapsack()

int main()

{

int value[6] = {3,6,7,9,11,18};

int weight[6] = {1,2,3,5,6,8};

int C = 100;

vector<int> pos;

int w = knapsack(value, weight, 6, 15);

cout << w << endl;

return 0;

}

**Complexity:**Computing each M(i , j) value will require Θ(nC) time as nC is the number of sub-problem of Θ(1) complexity each. Space complexity is also Θ(nC) if we save all the traversals and also want to know the individual items to be put in the knapsack.

Again as we have seen that at any point in time, we just need (i-1)

^{th}row’s values (M(i-1, j) and M(i-1, j-s

_{i})). So if we don’t want to know the individual items, space complexity will be linear as we only need to store current (i) and previous (i-1) row.

I am leaving the exercise of reconstructing, which all items to put in knapsack in order to achieve calculated optimal value, to readers.

Here is a well-explained video of solving of 0/1 knapsack problem with pen and paper.

**Subscribe**- To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
AnonymousI think there is a small typo in the last section of problem explanation..

Also if vi > j ; the current object i exceeds the capacity, we definitely can not pick it. So M(i, j) = M(i − 1, j) for this case.

It should be

Also if si > j ; the current object i exceeds the capacity, we definitely can not pick it. So M(i, j) = M(i − 1, j) for this case.

Similarly, it has to be changed in the recurrence equation as well

Well explained and nice code :-)

Akash@Anonymous: Thanks for pointing it out. I have corrected it now.