0Algorithm - Fractional Knapsack
import java.util.Scanner;
public class Knapsack01 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt(); // 1
int W = scan.nextInt(); // 1000
float value[] = new float[n]; // 500
float weight[] = new float[n]; // 30
float ratio[] = new float[n];
for (int i = 0; i < n; i++) {
value[i] = scan.nextInt();
weight[i] = scan.nextInt();
ratio[i] = value[i] / weight[i];
}
float totalValue = knapSack01(W, value, weight, ratio, n);
System.out.println(totalValue);
}
public static float knapSack01(float W, float[] value, floatweight[], float ratio[],
int n) {
float V = 0;
while (n>0 && W!=0) {
int mI = maxIndex(n, ratio);
float w=min(weight[mI],W);
// W=40,weight[2]=30 // W=10,weight[0]=20;
W = W - w;
V = V + w*ratio[mI];
weight[mI]=weight[mI]-w;
ratio[mI] = 0;
n--;
}
return V;
}
public static float min(float a,float b){
return a>b?b:a;
}
public static int maxIndex(int n, float ratio[]) {
float largest = Integer.MIN_VALUE;
int lastIndex = 0;
for (int i = 0; i < n; i++) {
if (ratio[i] > largest) {
largest = ratio[i];
lastIndex = i;
}
}
return lastIndex;
}
}
Output:
Input: 3 50
60 20 100
50 120 30
Output: 180.0000
