package fknapsack;
import java.io.*;
public class FKnapsack {
public static void main(String args[]) throws IOException {
BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter no of elements");
int no;
no = Integer.parseInt(obj.readLine());
int i;
int p[];
p = new int[no];
int w[];
w = new int[no];
for (i = 0; i < no; i++) {
System.out.println("Enter Profit of Obj " + (i + 1) + ":");
p[i] = Integer.parseInt(obj.readLine());
System.out.println("Enter Weight of Obj " + (i + 1) + ":");
w[i] = Integer.parseInt(obj.readLine());
}
System.out.println("Enter Capacity");
int c = Integer.parseInt(obj.readLine());
float pw[];
pw = new float[no];
for (i = 0; i < no; i++) {
pw[i] = (float) p[i] / w[i];
}
int j;
float temp;
int temp1;
for (i = 0; i < no; i++) {
for (j = i; j < no; j++) {
if (pw[i] < pw[j]) {
temp = pw[i];
pw[i] = pw[j];
pw[j] = temp;
temp1 = p[i];
p[i] = p[j];
p[j] = temp1;
temp1 = w[i];
w[i] = w[j];
w[j] = temp1;
}
}
}
float profit = 0;
float fraction;
float x[];
x = new float[no];
for (i = 0; i < no; i++) {
if (c - w[i] >= 0) {
c = c - w[i];
profit = profit + p[i];
x[i] = 1;
} else if (c != 0) {
fraction = (float) c / w[i];
profit = profit + (p[i] * fraction);
x[i] = fraction;
} else
break;
}
System.out.println("Profit:" + profit);
}
}
/* OUTPUT
Enter no of elements
5
Enter Profit of Obj 1:
10
Enter Weight of Obj 1:
2
Enter Profit of Obj 2:
5
Enter Weight of Obj 2:
6
Enter Profit of Obj 3:
3
Enter Weight of Obj 3:
4
Enter Profit of Obj 4:
2
Enter Weight of Obj 4:
3
Enter Profit of Obj 5:
11
Enter Weight of Obj 5:
7
Enter Capacity
20
Profit:29.666666
*/