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--------------------------------"); 
} 
}