19. DYNAMIC KNAPSACK PROBLEM

Code:

import java.util.*;

class DynKnapSack

{

    static void knapSack(int w[],int p[],int  n,int M)

     { int i,j;

       int  v[][]=new int[n+1][M+1];

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

          v[i][0]=0;

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

          for(j=1;j<=M;j++)

            {

                 if(i==1 ){

                    if( j>=w[i])

                              v[i][j]=p[i];

                   else

                             v[i][j]=0;

                          }

            else

                    if(j<w[i])

                                v[i][j]=v[i-1][j];

                    else

                              v[i][j]=Math.max(v[i-1][j],v[i-1][j-w[i]]+p[i]);

            }

         System.out.println("        TABLE   OF  PROFITS");

          System.out.println("=================================================");

           System.out.print("Weights: ");

           for(i=0;i<=M;i++)

              System.out.print(i+"    ");

          System.out.println();

         System.out.println("=================================================");

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

           {  System.out.print("Item:"+i+"  ");

              for(j=0;j<=M;j++)

                 if(v[i][j]<10)

                           System.out.print(" "+v[i][j]+"   ");

                  else

                          System.out.print(v[i][j]+ "   ");

              System.out.println();

           }

    //trace back

     int x[]=new int[n+1];j=M;

     for(i=n;i>0;i--)

        if(v[i][j]!=v[i-1][j]  &&v[i-1][j-w[i]]+p[i]==v[i][j]){j=j-w[i];x[i]=1;}

      

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

        System.out.println(x[i]);

       }

     public static void  main(String args[])

      {

Scanner sc=new Scanner(System.in);

          int w[]=new int[66];

          int  p[]=new int[66];

for(int i=0;i<=5;i++){

w[i]=sc.nextInt();}

for(int i=0;i<=5;i++){

p[i]=sc.nextInt();}

          int  M=11,n=5;

          knapSack(w,p,n,M);

       }

}

Need the code??

Download Link= https://www.dropbox.com/s/b2vjzv6tuz5zns9/DynKnapSack.txt