0/1 Knapsack – Dynamic Programming

import  java.util.*;

class knapsack_dynamic

{

                int n,p[],w[],capacity;

                void read()

                {

                                Scanner k=new Scanner(System.in);

                                System.out.println("Enter no. of objects:");

                                n=k.nextInt();

                                System.out.println("Enter capacity of knapsack:");

                                capacity=k.nextInt();

                                //create p and w array of size n+1

                               

                                p=new int[n+1];

                                w=new int[n+1];

                               

                                //read array w and p from 1 to n

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

                                {

                                                System.out.println("Enter weight of object " +i);

                                                w[i]=k.nextInt();

                                                System.out.println("Enter profit of object "+i);

                                                p[i]=k.nextInt();

                                                }

                                }//end read

                               

                                void fill()

                                {

                                                int c[][]=new int[n+1][capacity+1];

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

                                                c[i][0]=0;

                                               

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

                                               

                                                 for(int j=1;j<=capacity;j++)

                                                 

                                                  if(j-w[i] >=0)

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

                                                  else

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

                                                 

                                                  System.out.println("Maximum profit "+c[n][capacity]);

                                                  }//end fill

                                                 

                                                  }//end class Knapd

                                                 

                                                   class knapsac_dynamic

                                                  {

                                                                public static void main(String args[])

                                                                {

                                                                                knapd k=new knapd();

                                                                                k.read();

                                                                                k.fill();

                                                                }

                                                               

                                                 }

/*

 OUTPUT:

 Enter no. of objects:

 4

 Enter capacity of knapsack:

 5

 Enter weight of object 1

 2

 Enter profit of object 1

 3

 Enter weight of object 2

 3

 Enter profit of object 2

 4

 Enter weight of object 3

 4

 Enter profit of object 3

 5

 Enter weight of object 4

 5

 Enter profit of object 4

 6

 Maximum profit :7                                

 */