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 ith item type has an integer size si and a real value vi. You need to fill 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).
  1. If we don’t use ith item, then M(i , j) = M(i - 1 , j).
  2. If we use ith then M(i , j) = M(i - 1 , j – si) + vi

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 – si) + vi }

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.

Finally M(i, j) will be defined as
               0              if i = 0 or j = 0
M(i , j)   =    M(i-1, j)      if si > j
               max{ M(i - 1 , j) , M(i - 1 , j – si) + vi }   (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 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-si)). 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.