# KBest (POJ 3111)

Similar to Dropping Tests, this is a maximizing average value problem. The solution is:

import java.io.*;
import java.util.*;

class Jewel implements Comparable<Jewel> {

int i;
double v;
double w;
double r = 0.0;

public Jewel(int i, double v, double w) {
this.i = i;
this.v = v;
this.w = w;
}

public int compareTo(Jewel b) {
return (b.r - this.r > 0) ? 1 : -1;
}
}

public class KBest {
private static boolean valid(Jewel[] jewels, double avg, int k) {
for (Jewel j: jewels) j.r = j.v - j.w * avg;
Arrays.sort(jewels);
double sum = 0;
for (int i = 0; i < k; i++) sum += jewels[i].r;
return sum >= 0;
}
private static void solve(Jewel[] jewels, int k) {
double l = 0, u = 1000000.0;
for (int i = 0; i < 50; i++) {
double av = (l + u) / 2;
if (valid(jewels, av, k)) l = av;
else u = av;
}
int[] result = new int[k];
for (int i = 0; i < k; i++) result[i] = jewels[i].i;
Arrays.sort(result);
System.out.printf("%d", result[0]);
for (int i = 1; i < k; i++) System.out.printf(" %d", result[i]);
System.out.println();
}
public static void main(String[] args) throws IOException {