找零問題

問題描述：

給定總金額為n(n為正整數)和若幹面值為d1=1<d2<d3<...<dj...<dm的硬币（硬币數量無限），求用最小的硬币數湊足金額n的方案。

注：如果n<d1，那麼無法用現有的硬币面值找零，為規避這種情況，假定n>=d1；d1=1能夠保障任何正整數n都能被準确的找零。

分析：

為了驗證其最優子結構的性質，可以這樣考慮：

為了求解問題規模為n的最小硬币數量C(n)，向前思考一步，C(n)實際上可以認為是從問題規模為n-dj(滿足d1<=dj<=n)的基礎上在選取面值為dj的硬币而來。求解C(n)隻需要求解所有滿足條件的子問題n-dj中最小的C(n-dj)，那麼，C(n)在最小的C(n-dj)基礎上加1即可。

其遞推關系為：

動态規劃實作：

/*
     * 動态規劃實作
     * */
    public static int changeOfLessCoins(int[] ary,int n){
        int m = ary.length;
        int[] aux = new int[n+1];//aux[0]充當哨兵，沒事實際含義
        int tmpLest;
        for (int i = 1; i <= n; i++) {
            tmpLest = Integer.MAX_VALUE;
            for (int j = 0; j < m; j++) {
                if (i>=ary[j]) {
                    tmpLest = Math.min(aux[i-ary[j]], tmpLest);//目的在于找出一個最小的tmpLess
                }
            }
            aux[i] = tmpLest+1;
        }
        return aux[n];
    }      

貪心算法實作：

/*
     * 貪心算法實作
     * */
    public static int changeOfLessCoins(int[] ary,int n){
        int length = ary.length;
        int count  = 0;
        while(n>0){
            for (int i = length-1; i >= 0; i--) {//每次從最大的面值開始選擇
                if (ary[i]<=n) {
                    n -= ary[i];
                    count++;
                    break;
                }
            }
        }
        return count;
    }      

與找零問題類似的還有像完美平方問題：

給定一個正整數N，用最少的平方數（1,4,9,26,25...）使得其和等于N。

比如N=13，最少的平方數為13=4+9,隻需要4和9兩個平方數即可。

參考資料：

算法按設計與分析基礎.第三版.第十五章