Knapsack Problem > Java Program
Analysis of Algorithm
Knapsack Problem > Java Program
import java.io.*;
class knapsack
{
public static void main(String args[])throws IOException
{
DataInputStream in=new DataInputStream(System.in);
int i,j;
double p1=0.0;
System.out.println("Enter NO of Elements");
int n=Integer.parseInt(in.readLine());
System.out.println("Enter Capacity");
float w1=Integer.parseInt(in.readLine());
float w[]=new float[n];
float p[]=new float[n];
System.out.println("Enter Profit AND WEIGHT");
for(i=0;i<n;i++)
{
System.out.print("Profit of "+(i+1)+" ");
p[i]=Integer.parseInt(in.readLine());
System.out.print("Weight of "+(i+1)+" ");
w[i]=Integer.parseInt(in.readLine());
}
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(p[j]/w[j] < p[j+1]/w[j+1])
{
float 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;
}
}
}
for(i=0;i<n;i++)
{
if(w[i]<=w1)
{
w1=w1-w[i];
p1=p1+p[i];
}
else
{
if(i<=n&&w1!=0)
{
p1=p1+w1*(p[i]/w[i]);
}
}
}
System.out.println("--------------------------------");
System.out.println("Proft is "+p1);
System.out.println("\n--------------------------------");
}
}
Comments
Post a Comment