0/1 Knapsack Problem 

Statement:
A thief has a bag or knapsack that can contain maximum weight W of his loot. There are n items and the weight of ith item is wi and it worth vi. An amount of item can be put into the bag is 0 or 1 i.e. xi is 0 or 1. Here the objective is to collect the items that maximize the total profit earned.


0/1 Knapsack Problem Statement
The algorithm takes as input maximum weight W, the number of items n, two arrays v[] for values of items and w[] for weight of items. Let us assume that the table c[i,w] is the value of solution for items 1 to i and maximum weight w. Then we can define recurrence relation for 0/1 knapsack problem as
0/1 Knapsack Problem Statement

Algorithm:



DynaKnapsack(W,n,v,w)

{

for(w=0; w<=W; w++) 

C[0,w] = 0;

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

C[i,0] = 0;

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

{

 for(w=1; w<=W;w++)

{ 

if(w[i]<w)

{

if v[i] +C[i-1,w-w[i]] > C[i-1,w]

{ 

C[i,w] = v[i] +C[i-1,w-w[i]];

}

else

{

C[i,w] = C[i-1,w];     

}   

} 

else   

{

C[i,w] = C[i-1,w]; 

}

}             

}

}

Analysis

For run time analysis examining the above algorithm the overall run time of the algorithm is O(nW).

 Example:


0/1 Knapsack Problem Statement