KnapSack Problem Program

KnapSack Problem Program:


import java.util.Scanner;
class KnapSack
{
        static int i[]={1,2,3,4,5,6};
        static int w[]={2,3,1,5,3,2};
        static int v[]={6,4,3,7,5,4};
        public static void main(String args[])
        {
                Scanner sc=new Scanner(System.in);
                System.out.println("Enter KnapSack Size");
                int size=sc.nextInt();
                float temp[]=new float[i.length];
                float sum=0;
                for(int x=0;x<=i.length-1;x++)
                {
                        temp[x]=(float)v[x]/w[x];
                }
                insertion_sort(temp);
                for(int x=0;x<=i.length-1;x++)
                {
                        if(size >= w[x])
                        {
                                sum=sum+v[x];
                                size=size-w[x];
                        }
                        else
                        {
                                sum=sum+(v[x]*(float)size/w[x]);
                                size=0;
                        }
                }
                System.out.println(sum);
        }

        public static void insertion_sort(float ar[])
        {
                for(int x=1;x<=ar.length-1;x++)
                {
                        int j=x-1;
                        float temp1=ar[x];
                        int temp2=i[x];
                        int temp3=w[x];
                        int temp4=v[x];
                        while(j>=0 && ar[j]<temp1)
                        {
                                ar[j+1]=ar[j];
                                i[j+1]=i[j];
                                w[j+1]=w[j];
                                v[j+1]=v[j];
                                j=j-1;
                        }
                        ar[j+1]=temp1;
                        i[j+1]=temp2;
                        w[j+1]=temp3;
                        v[j+1]=temp4;
                }
        }
}

Post a Comment

0 Comments