Algorithm筆記 10.3 - greedy演算法練習: 注意眉角

如果你也在修Coursera Algorithm Toolbox的話，這是解答！請斟酌使用

本來這題功課沒什麼好po的，但是有個implementation眉角要注意，所以寫出來警惕一下。下面粉色標出的區塊就是Java comparator的實作，但是由於compare要回傳int，所以不能直接把o2 - o1的值cast成int回傳，這樣可能會變成零，如果兩者的差<1.0的話。

public class FractionalKnapsack {
    private static double getOptimalValue(int capacity, int[] values, int[] weights) {
        double value = 0;

        class Item {
            public int value;
            public int weight;
            public double valuesPerWeight;

            public Item(int value, int weight) {
                this.value = value;
                this.weight = weight;
                this.valuesPerWeight = (double)value / (double)weight;
            }
        }

        //O(n) initalization        
        Item[] items = new Item[values.length];
        for (int i = 0; i < items.length; i++) {
            items[i] = new Item(values[i], weights[i]);
        }

        //O(nlogn) sort        
        Arrays.sort(items, new Comparator<Item>() {
            @Override            
            public int compare(Item o1, Item o2) {
                if (o2.valuesPerWeight - o1.valuesPerWeight > 0)
                    return 1;
                else if (o2.valuesPerWeight - o1.valuesPerWeight < 0)
                    return -1;
                else return 0;
            }
        });

        for(int i = 0; i < items.length; i++) {
            double load = Math.min((double)capacity, (double)items[i].weight);

            if (load >= items[i].weight) { //use all items[i]                
                value += items[i].value;
                capacity -= load;
            }
            else { //use fracation of items[i]                
                value += load * items[i].valuesPerWeight;
                return value;
            }
        }

        return value;
    }

    public static void stressTest() {
        while (true) {
            int n = ThreadLocalRandom.current().nextInt(1, 1000);
            int capacity = ThreadLocalRandom.current().nextInt(0, 2000000);
            int[] values = new int[n];
            int[] weights = new int[n];

            for (int i = 0; i < n; i++) {
                values[i] = ThreadLocalRandom.current().nextInt(0, 2000000);
                weights[i] = ThreadLocalRandom.current().nextInt(0, 2000000);
            }

            System.out.println(getOptimalValue(capacity, values, weights));
        }
    }

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int capacity = scanner.nextInt();
        int[] values = new int[n];
        int[] weights = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = scanner.nextInt();
            weights[i] = scanner.nextInt();
        }
        System.out.println(getOptimalValue(capacity, values, weights));

        //stressTest();    
    }