Thursday, April 14, 2011

Knapsack – Greedy algorithm


import java.io.*;
class greedy
{
        int n;
        double m,p[],w[];
        void read()throws IOException
        {
                        DataInputStream d=new DataInputStream(System.in);
                        System.out.println("enter no of objects");
                        n=Integer.parseInt(d.readLine());
                        System.out.println("enter total capacity");
                        m=Double.parseDouble(d.readLine());
                        p=new double[n+1];
                        w=new double[n+1];
                        for(int i=1;i<=n;i++)
                        {
                                        System.out.println("enter weight of obj "+i);
                                        w[i]=Double.parseDouble(d.readLine());
                                        System.out.println("enter profit of obj "+i);
                                        p[i]=Double.parseDouble(d.readLine());
                        }
        }
        void sort()
        {
                        for(int i=n-1;i>=1;i--)
                        for(int j=1;j<=i;j++)
                       
                        if(p[j]/w[j] < p[j+1]/w[j+1])
                        {
                                        double t;
                                        t=p[j];
                                        p[j]=p[j+1];
                                        p[j+1]=t;
                                        t=w[j];
                                        w[j]=w[j+1];
                                        w[j+1]=t;
                        }
        }
       
        void fill()
        {
                        int x[]=new int[n+1];
                        int i;
                        double profit=0.0;
                        for( i=1;i<=n;i++)
                        x[i]=0;
                       
                        for( i=1;i<=n;i++)
                        {
                                        if(m-w[i]>=0)
                                        {
                                                       
                              m=m-w[i];
                              profit=profit+p[i];
                              x[i]=1;
                            }
                            else
                            break;
                         }
                         
                         if(m!=0)
                         {
                                        profit=profit+(p[i]/w[i])*m;
                         }
                         
                         System.out.println("max profit is = "+profit);
                        }
        }
        public class knapsack
        {
                        public static void main(String args[])throws IOException
                        {
                                       
                          greedy g=new greedy();
                          g.read();
                          g.sort();
                          g.fill();
}
}

output:
enter no of objects
3
enter total capacity
5
enter weight of obj 1
10
enter profit of obj 1
20
enter weight of obj 2
13
enter profit of obj 2
29
enter weight of obj 3
14
enter profit of obj 3
27
max profit is = 11.15
Press any key to continue...