一、貪心算法

什么情況下我們要想到用貪心算法：

1、當(dāng)我們看到這類問題的時(shí)候，首先要聯(lián)想到貪心算法：針對(duì)一組數(shù)據(jù)，我們定義了限制值和期望值，希望從中選出幾個(gè)數(shù)據(jù)，在滿足限制值的情況下，期望值最大；
2、我們嘗試看下這個(gè)問題是否可以用貪心算法解決：每次選擇當(dāng)前情況下，在對(duì)限制值同等貢獻(xiàn)量的情況下，對(duì)期望值貢獻(xiàn)最大的數(shù)據(jù) 。
3、我們舉幾個(gè)例子看下貪心算法產(chǎn)生的結(jié)果是否是最優(yōu)的。大部分情況下，舉幾個(gè)例子驗(yàn)證一下就可以
了。
注意：不要刻意去記憶貪心算法的原理，要多練習(xí)；不要嚴(yán)謹(jǐn)?shù)淖C明算法，多舉幾個(gè)例子驗(yàn)證一下！
我們用幾個(gè)案例來理解貪心算法。
1、有一個(gè)可以裝100kg物品的箱子，我們有5種物品（大米100kg，總價(jià)值100元； 玉米30kg，總價(jià)值90元；小麥60kg，總價(jià)值120元；芝麻20kg，總價(jià)值80元；大豆50kg，總價(jià)值75元），為了讓箱子中所裝物品的總價(jià)值最大，在箱子中要選擇哪些物品，每種物品的要裝多少？
這個(gè)問題我們可以直接算出來，在箱子裝20kg芝麻、30kg玉米、50kg小麥。
代碼實(shí)現(xiàn)如下：

  /**
     * 箱子價(jià)值最大化
     *
     * @param w 物品重量
     * @param v 物品價(jià)值
     * @param n 物品數(shù)量
     * @param m 背包承受重量
     */
    public void boxLoading(int[] w, int[] v, int n, int m) {
        // 計(jì)算每個(gè)物品的單價(jià)
        float[] p = new float[n];
        // 記錄物品排序后的下標(biāo)
        int[] idxs = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = v[i] / (float) w[i];
            idxs[i] = i;
        }

        // 將單價(jià)按降序排序
        for (int i = 0; i < n; i++) {
            // 排序完成標(biāo)識(shí)
            boolean flag = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (p[j] < p[j + 1]) {
                    float temp = p[j];
                    p[j] = p[j + 1];
                    p[j + 1] = temp;
                    flag = true;
                    int index = idxs[j];
                    idxs[j] = idxs[j + 1];
                    idxs[j + 1] = index;
                }
            }
            if (!flag) {
                break;
            }
        }

        // 將重量和總價(jià)值降序排序
        int[] w1 = new int[n];
        int[] v1 = new int[n];
        // 每個(gè)物品的放到箱子的重量
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            w1[i] = w[idxs[i]];
            v1[i] = v[idxs[i]];
            res[i] = 0;
        }

        // 箱子剩余可放入重量
        int cu = m;
        // 計(jì)算每個(gè)物品要放入重量
        for (int i = 0; i < n; i++) {
            // 物品重量大于等于可放入的重量
            if (w1[i] >= cu) {
                // 還有剩余空間
                if (cu > 0) {
                    res[i] = cu;
                }
                break;
            } else {
                // 否則，把當(dāng)前物品全部裝入箱子中
                cu = cu - w1[i];
                res[i] = w1[i];
            }
        }

        // 輸出裝入箱子的物品的重量
        for (int i = 0; i < n; i++) {
            int idx = idxs[i] + 1;
            System.out.println("第" + idx + "個(gè)物品，重量為：" + res[i]);
        }
    }

2、分糖果
我們有m個(gè)糖果和n個(gè)孩子（m<n）。每個(gè)糖果的大小不等，每個(gè)小孩對(duì)糖果的需求也是不一樣的，如何分配糖，能盡可能滿足最多數(shù)量的孩子。

我們可以從n個(gè)孩子中，抽取一部分分配糖果，讓滿足的孩子的個(gè)數(shù)（期望值）是最大的。限制值就是糖果個(gè)數(shù)m。

我們每次從剩下的孩子中，找出對(duì)糖果大小需求最小的，然后發(fā)給他剩下的糖果中能滿足他的最小的糖果，這樣得到的分配方案，也就是滿足孩子個(gè)數(shù)最多的方案。代碼實(shí)現(xiàn)如下：

/**
     * 分糖果
     * @param candies 糖果大小
     * @param reqs  孩子需求量
     * @return 孩子數(shù)量
     */
    public int divideCandy(int[] candies, int[] reqs) {
        int m = candies.length;
        int n = reqs.length;

        // 對(duì)糖果和孩子的需求排序
        insertSort(candies);
        insertSort(reqs);
        // 假設(shè)每個(gè)小孩只能獲得一棵糖果
        int[] children = new int[n];
        // 記錄孩子個(gè)數(shù)
        int count = 0;

        int i = 0;
        int j = 0;
        while (i < m) {
            // 糖果的大小要大于等于當(dāng)前需求才滿足
            if (candies[i] >= reqs[j]) {
                children[j] = reqs[j];
                count++;
                j++;
            }
            i++;
        }
        return count;
    }

    // 插入排序
    private void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int value = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (arr[j] > value) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
            }
            arr[j + 1] = value;
        }
    }

3、錢幣找零
假設(shè)我們有1元、2元、5元、10元、20元、50元，100元這些面額的紙幣，它們的張數(shù)分別是c1、c2、c5、c20、c50、c100。我們現(xiàn)在要用這些錢來支付K元，最少要用多少張紙幣呢？

在貢獻(xiàn)相同期望值（紙幣數(shù)目）的情況下，我們希望多貢獻(xiàn)點(diǎn)金額，這樣就可以讓紙幣數(shù)量更少，這是一種貪心算法的解決思路。代碼如下：

  /**
     * 零錢找零
     *
     * @param moneys  錢面額
     * @param amounts 每張面額數(shù)量
     * @param k       要支付多少錢
     * @return 要找多少張錢
     */
    public int coinChange(int[] moneys, int[] amounts, int k) {
        int n = moneys.length;
        // 記錄金額
        int cur = 0;
        // 記錄錢幣的數(shù)量
        int count = 0;
        // 記錄需要哪些面額
        int[] m1 = new int[n];
        // 記錄需要面額的張數(shù)
        int[] a1 = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            // 從最大的錢幣開始判斷是否滿足
            int money = moneys[i];
            m1[i] = money;
            // 如果錢幣的面積大于k,直接到下一個(gè)
            if (money > k) {
                continue;
            }
            int amount = amounts[i];
            int tmep = 0;
            // 累計(jì)的錢加上當(dāng)前面額小于等于k，說明這張錢可以找出去
            while (cur + money <= k && amount >= 0) {
                cur += money;
                amount--;
                count++;
                tmep++;
            }
            a1[i] = tmep;
            // 零錢已經(jīng)找好了
            if (cur == k) {
                break;
            }
        }
        return count;
    }

4、區(qū)間覆蓋
假設(shè)我們有n個(gè)區(qū)間，區(qū)間的起始端點(diǎn)和結(jié)束端點(diǎn)分別是【l1, r1]，[l2, r2]，[l3, r3]，...，[ln, rn]。從這n個(gè)區(qū)間中選出一部分區(qū)間，這部分區(qū)間滿足兩兩不相交（端點(diǎn)相交的情況不算相交），最多能選出多少個(gè)區(qū)間呢？

比如，區(qū)間：[6, 8], [2, 4], [3, 5], [1,5], [5, 9], [8, 10]; 不相交的區(qū)別有：[2, 4], [6, 8], [8, 10]

這個(gè)處理思想在很多貪心算法問題中都有用到，像任務(wù)調(diào)度、教師排課。

解決思路：假設(shè)這n個(gè)區(qū)間中最左端點(diǎn)是lmin,最右端點(diǎn)是rmax。我們選擇幾個(gè)不相交的區(qū)別，從左到右[lmin, rmax]覆蓋上（如下圖）。我們按照起始端點(diǎn)從小到大順序?qū)@幾個(gè)區(qū)間排序。從圖可以看出，我們每次選擇的時(shí)候，左端點(diǎn)跟前面的已經(jīng)覆蓋的區(qū)間不重合，右端點(diǎn)又盡量小的，這樣可以讓剩下的未覆蓋區(qū)間覆蓋盡可能的大，就可以放置更多的區(qū)間。

代碼實(shí)現(xiàn)如下：

 /**
     * 區(qū)間覆蓋
     *
     * @param arr 區(qū)間數(shù)組
     * @return 滿足兩兩不相交區(qū)間
     */
    public int[][] intervalCoverage(int[][] arr) {
        int n = arr.length;
        // 對(duì)數(shù)組按左端點(diǎn)進(jìn)行排序
        selectSort(arr);
        int[][] res = new int[n][2];
        int left = arr[0][0];
        int right = arr[0][1];
        // 記錄右端點(diǎn)最小的區(qū)間
        int index = 0;
        for (int i = 1; i < n; i++) {
            // 判斷是否是相交的區(qū)間,左端點(diǎn)在區(qū)間中,說明相交
            if (arr[i][0] >= left && arr[i][0] < right) {
                // 判斷是右端點(diǎn)小于等于right
                if (arr[i][1] <= right) {
                    right = arr[i][1];
                    index = i;
                }
            } else {
                // 如果不相交，再以這個(gè)區(qū)間與下個(gè)區(qū)間進(jìn)行比較
                left = arr[i][0];
                right = arr[i][1];
                // 將上一次相交的區(qū)間的右端點(diǎn)加到結(jié)果中
                res[index] = arr[index];
                // 更新index
                index = i;
            }
        }
        // 如果最后區(qū)間就是最小右端點(diǎn)
        if (index == n - 1) {
            res[index] = arr[index];
        }
        return res;
    }

    // 選擇排序
    private void selectSort(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[min][0] > arr[j][0]) {
                    min = j;
                }
            }
            int[] temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }

5、霍夫曼編碼
假設(shè)有一個(gè)包含1000個(gè)字符的文件，每個(gè)字符占1個(gè)byte(1byte=8bits),存儲(chǔ)這1000個(gè)字符一共需要8000bits，那有沒有節(jié)省空間的存儲(chǔ)方式呢？

假設(shè)通過統(tǒng)計(jì)分析發(fā)現(xiàn)，這1000個(gè)字符只包含6個(gè)不同的字符，假設(shè)它們分別是a, b, c, d, e, f。而3個(gè)二進(jìn)制位就可以表示8個(gè)不同的字符，所以為了盡量減少存儲(chǔ)空間，每個(gè)字符我們用3個(gè)二進(jìn)制來表示。那存儲(chǔ)1000個(gè)字符只需要3000bits就可以了。
a(000)、b(001)、c(010)、d(011)、e(100)、f(101)

二進(jìn)制的存儲(chǔ)方式，確實(shí)節(jié)省了很多空間。不過還更節(jié)省存儲(chǔ)方式：霍夫曼編碼，它是一種十分有效的編碼方法，廣泛用于數(shù)據(jù)壓縮中，其壓縮率通常在20%~90%之間。

霍夫曼編碼是不等長的，每次應(yīng)該讀取1位還是2位、3位等等來解壓縮呢？這個(gè)問題會(huì)導(dǎo)致霍夫曼編碼解壓縮的時(shí)候比較復(fù)雜。為了避免解壓縮過程中的歧義，霍夫曼編碼要求各個(gè)字符的編碼之間，不會(huì)出現(xiàn)某個(gè)編碼是另一個(gè)編碼前綴的情況。

我們把字符編碼下面這個(gè)樣子，任何一個(gè)字符的編碼都不是另一個(gè)前綴，在解壓縮的時(shí)候，每次讀取盡可能長的可解壓的二進(jìn)制串，所以在解壓縮的時(shí)候也不會(huì)歧義。經(jīng)過這種編碼壓縮之后，這1000個(gè)字符只需要2100bits就可以了。

怎么根據(jù)字符出現(xiàn)頻率的不同，給不同的字符進(jìn)行不同長度的編碼呢？

我們把每個(gè)字符看作一個(gè)節(jié)點(diǎn)，并且附帶著頻率放到優(yōu)先隊(duì)列中。我們從隊(duì)列中取出頻率最小的兩個(gè)節(jié)點(diǎn)A、B，然后新建一個(gè)節(jié)點(diǎn)C，把頻率設(shè)置為兩個(gè)節(jié)點(diǎn)的頻率之后，并把這個(gè)新節(jié)點(diǎn)作為A、B節(jié)點(diǎn)的父節(jié)點(diǎn)。最后再把C節(jié)點(diǎn)放入到優(yōu)先級(jí)隊(duì)列中。重復(fù)這個(gè)過程，直到隊(duì)列中沒有數(shù)據(jù)。

現(xiàn)在我們給每一邊邊上畫上一個(gè)權(quán)值，指向左子節(jié)點(diǎn)的邊我們統(tǒng)統(tǒng)標(biāo)記為0，指向右子節(jié)點(diǎn)的邊，統(tǒng)統(tǒng)標(biāo)記為1，從根節(jié)點(diǎn)到時(shí)葉節(jié)點(diǎn)的路徑就是葉節(jié)點(diǎn)對(duì)應(yīng)字符的霍夫曼編碼。