題目（算法課第八課）

一塊金條切成兩半，是需要花費(fèi)和長度數(shù)值一樣的銅板的。比如長度為20的 金條，不管切成長度多大的兩半，都要花費(fèi)20個(gè)銅板。一群人想整分整塊金 條，怎么分最省銅板？

例如,給定數(shù)組{10,20,30}，代表整塊金條長度為10+20+30=60. 金條要分成10,20,30三個(gè)部分。
如果， 先把長度60的金條分成10和50，花費(fèi)60 再把長度50的金條分成20和30，花費(fèi)50 一共花費(fèi)110銅板。但是如果， 先把長度60的金條分成30和30，花費(fèi)60 再把長度30金條分成10和20，花費(fèi)30 一共花費(fèi)90銅板。

給定數(shù)組{10,20,30}

輸入一個(gè)數(shù)組，返回分割的最小代價(jià)。

分析

這是一個(gè)典型的哈夫曼問題，哈夫曼的思想就是這個(gè)題目的貪心策略。

做法

1. 從一組數(shù)據(jù)里面每次拿出最小的兩個(gè)數(shù)
2. 相加再放進(jìn)數(shù)組里

• 直到只剩下一個(gè)數(shù)據(jù)為止
• 他的所有葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的代價(jià)一定是最小的

代碼實(shí)現(xiàn)

import java.util.PriorityQueue;

public class LessMoney{
    public static int lessMoney(int[]arr){
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); //使用優(yōu)先級隊(duì)列
        int res = 0;
        int cur = 0;
        for (int i = 0; i < arr.length; i++) {
            pq.add(arr[i]);
        }
        while(pq.size()>1){
        //1-------------------------------------------------------------
            cur = pq.poll()+pq.poll();
            res += cur;
       //2-------------------------------------------------------------
            pq.add(cur);
        }
        return res;
    }
    public static void main(String[] args) {
        int arr[] = new int[] { 10, 20, 30 };//90
        System.out.println(lessMoney(arr));
    }
}

測試結(jié)果