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?

Solution:

 
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
 

Algorithm:

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]
                                                else
                                                                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 */
 
#include<stdio.h>
 
/* 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;
   intV[n+1][W+1];
 
/* 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]);
           else
                 V[i][w] = V[i-1][w];
       }
   }
 
   returnV[n][W];
}

Time complexity:

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

Go to top