Description: Given a knapsack with maximum capacity W, and a set S consisting of n items Each item i has some weight wi and benefit value bi  (all wi  and W are integer values)  Problem: How to pack the knapsack to achieve maximum total value of packed items?


Recursive formula :
where V[k,w] denotes an optimal solution for Sk = {items labeled 1, 2, .. k} in a knapsack of size w
The above formula means that the best subset of Sk that has total weight w is:
1) the best subset of Sk-1 that has total weight £ w,    or
2) the best subset of Sk-1 that has total weight £ w- wk plus the item k


for w = 0 to W
                V[0,w] = 0
for i = 1 to n
                V[i,0] = 0
for i = 1 to n
                for w = 1 to W
                                if wi <= w /* item i can be part of the solution */
                                                if bi + V[i-1,w-wi] > V[i-1,w]
                                                                V[i,w] = bi + V[i-1,w- wi]
                                                                V[i,w] = V[i-1,w]
                                else V[i,w] = V[i-1,w]  // wi > w

C Implementation:

/* A Dynamic Programming based solution for 0-1 Knapsack problem */
/* A utility function to calculate maximum of two integers */
int max(inta, intb) { return(a > b)? a : b; }
/* Returns the maximum value that can be put in a knapsack of capacity W */
int knapSack(int W, int wt[], int val[], int n)
   inti, w;
/* Build table V[][] in bottom up manner */
for(i = 0; i <= n; i++)
       for(w = 0; w <= W; w++)
           if(i==0 || w==0)
               V[i][w] = 0;
           elseif(wt[i-1] <= w)
                 V[i][w] = max(val[i-1] + V[i-1][w-wt[i-1]],  V[i-1][w]);
                 V[i][w] = V[i-1][w];

Time complexity:

O(nW) where n is the number of items and W is the capacity of knapsack.

Go to top