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...
No comments:
Post a Comment