Thursday, April 14, 2011

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                                
 */