Dynamic Programming - 0/1 Knapsack Problem

➤ Greedy algo does not give optimal solution everytime.
     Exa. Consider  n=3 and Capacity W=30
              w={20,10,5}
              p={180,80,50}
              p/w={9,8,10}
              greedy solution={1,0,1} ➝ profit =180+50=230
              optimal solution={1,1,0} ➝ profit=180+80=260

Algo :- 

• w[i] gives weight of ith item.
• p[i] gives value(profit) of ith item.
• sol[i][j] gives the maximum profit for i items and j capacity(sub problem)

Use Desktop Version Of This Site For Better View.

for(j=0 to m) ➝ No Capicity No Packets

     sol[0][j]=0

for(i=0 to m) ➝ No Items

     sol[i][0]=0

for(i=1 to n) 

     for(j=1 to m)

          if(w[i] > j)                     ➝ ith item not selected because weight of the 

              sol[i][j]=sol[i-1][j]         ith item  is more than available capacity

          else                               ➝ select ith item if total profit with ith item is 

                                                     more  than profit without ith item

              sol[i][j]=max{sol[i-1][j] , sol[i-1][j-w[i]]+p[i]}

Programme :- 

Download the programme

#include<stdio.h>
int findmax(int x,int y)
{
    int max=x;
    if(y>max)
    {
        max=y;
    }
    return max;
}
main()
{
    int n,i,j;
 printf("ENTER THE TOTAL ITEMS : ");
 scanf("%d",&n);
 int w[n],p[n],W;
 for(i=0;i<n;i++)
 {
  printf("ITEM NO.%d\nWEIGHT : ",(i+1));
  scanf("%d",&w[i]);
  printf("VALUE : ");
  scanf("%d",&p[i]);
 }
 printf("ENTER THE MAXIMUM CAPACITY OF KNAPSACK : ");
 scanf("%d",&W);

    int sol[n+1][W+1];
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=W;j++)
        {
            if (i==0 || j==0)
            {
                sol[i][j]=0;
            }
            else if(w[i-1]>j)
            {
                sol[i][j]=sol[i-1][j];
            }
            else
            {
                sol[i][j]=findmax(sol[i-1][j],sol[i-1][j-w[i-1]]+p[i-1]);
            }
           // printf("sol[%d][%d] : %d\t",i,j,sol[i][j]);
        }
        //printf("\n");
    }
    i=n;
    j=W;
    while(i>0 && j>0)
    {
        if(sol[i][j]>sol[i-1][j])
        {
            printf("ITEM[%d] IS SELECTED.\n",i);
            j=j-w[i-1];

        }
        i--;
    }
    printf("PROFIT : %d",sol[n][W]);
}

Analysis : 

• Algo takes O(n*W) time as the size of sol array is n*w where n is the number of items and W is the capacity of knapsack.
• It is not polynomial time algorithm.
• It is Pseudo-polynomial algorithm.
• Pseudo-polynomial algorithm : - An algorithm whose worst case time complexity depends on numeric value of input (not number of inputs) is called Pseudo-polynomial algorithm.