PROGRAMMING INTERVIEWS

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 fill a knapsack of total capacity C with a selection of items of maximum value. You can add multiple items of the same type to the knapsack.

Answer: This problem is a perfect example of Dynamic Programming. We should construct the sub-problems and build our main answer using that. This can also be solved using greedy/brute-force as well. But time complexity will be horrendous and we can’t surely say if we filled the knapsack with maximum value.

Let M(j) denote the maximum value you can pack into a size j knapsack. Lets see if we can compute M(j) using M(1… j-1) for j from 1 to C.

What can be best possible value for M(j)?

Lets denote knapsack of capacity j as an array of length j and put weight at each slot, if possible. Then maximum possible M(j) = M(j-1) if j^th slot is empty.

Else if j^th slot isn’t empty and we fill j^th slot with item i then maximum possible M(j) = max_i=1...n M(j − s_i) + v_i

Now, we can express M(j) recursively in terms of solutions to smaller problems as follows:

M(j) = max{M(j − 1), max_i=1...n M(j − s_i) + v_i} if j ≥ 1

else

M(j) = 0 if j≤ 0

If we just do this, we will come to know what is the maximum possible value we can put in knapsack. But we will not know which items. We can reconstruct the list of items in the optimal solution by maintaining and following “backpointers”.

Code:

int knapsack(int value[], int weight[], int n, int C, vector<int> backtrack)
{
 int *M = new int[C+1];
 int i, j, tmp, pos;
 for(i=1; i<= C; i++)
 {
     M[i] = M[i-1];
     pos = i-1;             
     for(j=0; j< n; j++)
     {
         if (i >= weight[j])
             tmp = M[i-weight[j]] + value[j];
         if (tmp > M[i]){
             M[i] = tmp;
             pos = i - weight[j];
         }
     }
     backtrack.push_back(pos);
 } 
 int ans = M[C];
 delete[] M;      
 return ans;
}

I'm leaving the exercise of finding the elements from backtrack vector to users.

Complexity: Computing each M(j) value will require Θ(n) time, and we need to sequentially compute C such values. Therefore, total running time is Θ(nC). Total space is Θ(C). The value of M(C) will contain the value of the optimal knapsack packing.
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.