Algorithm筆記 10.5 - greedy演算法練習: 將一數拆成找出最多相異數字

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

問題定義

如何將某數n拆成最多個相異正整數？例如6可以拆成{1,2,3}，10可以拆成{1,2,3,4}。

看起來可以提出一個safe move的假設，“永遠從目前最小的未選過的正整數開始”。

證明safe move

假設一數n，其optimal solution為拆成m個數 n = k1 + k2 + k3 + ... + km，且a < k1 < k2 < ... < km。令 x = k1 - a。

我們很輕易可以改寫成以下：
n = (k1-x) + k2 + ... + (km+x)，也是一個optimal solution，因為k1-x = a < k2 < ... <km < km+x，都是相異自然數，故此策略為safe move

實作

選取最小正整數a有一個條件，就是n' = n-a >= a+1 = a'，這樣在下一個subproblem中最小能選的數a'才能小於等於n'，才有解。
舉例來說，8要怎麼拆成最多個正整數相加？按照我們演算法：

8-1 = 7, (7 >= 2)
7-2 = 5, (5 >= 3)
5-3 = 2, (2 < 4)
5-4 = 1, (1 < 5)
5-5 = 0, (分配完畢）

private static List<Integer> optimalSummands(int n) {
    List<Integer> summands = new ArrayList<Integer>();

    //find the min    int min = 1;
    while(n != 0) {
        int a = n - min;

        if (a == 0 || a >= min+1) {
            summands.add(min);
            n = a;
        }

        min = min + 1;
    }

    //write your code here    return summands;
}

running time為O(n)。