maxIndex

gistfile1.txt

// result: 0.10666666666666667
public class Result {

    static double result = 0;

    public static void main(String[] args) {
        User[] raw = {new User(0.1, 75), new User(0.16, 74.9),
                new User(0.11, 74.8), new User(0.12, 74.4),
                new User(0.09, 74.4), new User(0.07, 74.3),
                new User(0.09, 74.2), new User(0.09, 74.2),
                new User(0.07, 74.2), new User(0.11, 74.1)};

        User[] expUsers = {new User(0.21, 78.2), new User(0.3, 74), new User(0.25, 70.4)};

        System.out.println(maxIndex(raw, expUsers));
    }

    private static double maxIndex(User[] raw, User[] expUsers) {
        int k = expUsers.length;

        double sum = 0;
        for (User e : expUsers) {
            sum += e.age;
        }
        double avg = sum / k;
        dfs(raw, 0, avg, k, k, 0.0, 0.0);

        return result;
    }

    private static void dfs(User[] raw, int index, double avg, int k, int remain, double currentAgeSum, double currentIndexSum) {
        if (remain == 0) {
            if (Math.abs(((currentAgeSum) / k) - avg) <= 0.1) {
                result = Math.max(result, currentIndexSum / k);
            }
            return;
        }
        if (index >= raw.length || remain > raw.length - index) return;

        //not select
        dfs(raw, index + 1, avg, k, remain, currentAgeSum, currentIndexSum);
        //select
        dfs(raw, index + 1, avg, k, remain - 1, currentAgeSum + raw[index].age,
                currentIndexSum + raw[index].index);
    }

    static class User {
        public User(double index, double age) {
            this.index = index;
            this.age = age;
        }
        double index;
        double age;
    }
}