ADS

0/1 Knapsack Problem | DAA


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


Post a Comment

0 Comments