大家好，最近由于剛剛?cè)肼氁龅氖虑楹芏?，疏于更新一段時(shí)間，從今天開(kāi)始，我會(huì)慢慢恢復(fù)更新，與大家分享一些算法方面的經(jīng)驗(yàn)。

好久沒(méi)說(shuō)動(dòng)態(tài)規(guī)劃了，經(jīng)過(guò)上次的分析，大家應(yīng)該已經(jīng)對(duì)動(dòng)態(tài)規(guī)劃有了個(gè)大體的認(rèn)識(shí)，今天我們一起來(lái)看一個(gè)經(jīng)典的問(wèn)題--0/1背包問(wèn)題?？赡苡行┩瑢W(xué)覺(jué)得背包問(wèn)題很簡(jiǎn)單，無(wú)非寫(xiě)個(gè)判斷條件，遞歸執(zhí)行就能解決。但是想要拿到最優(yōu)解，我們?nèi)匀挥性S多需要細(xì)細(xì)思量的東西。

我們先來(lái)看一下題目的定義：給定N種水果的重量跟收益，我們需要把它們放進(jìn)一個(gè)可容重量為C的背包里，使得包里的水果在總重量不超過(guò)C的同時(shí)擁有最高的收益，假設(shè)水果數(shù)量有限，一種只能選一個(gè)。

題目很短，很容易理解，我們?cè)倬唧w化一點(diǎn)，看一個(gè)例子。假設(shè)我現(xiàn)在要去賣(mài)水果，現(xiàn)在的情況如下：
水果: { 蘋(píng)果, 橙子, 香蕉, 西瓜 }
重量: { 2, 3, 1, 4 }
收益: { 4, 5, 3, 7 }
背包可容重量: 5

先來(lái)試試不同的組合的結(jié)果：
蘋(píng)果 + 橙子 (總重量5) => 9
蘋(píng)果 + 香蕉 (總重量 3) => 7
橙子 + 香蕉 (總重量 4) => 8
香蕉 + 西瓜 (總重量 5) => 10

我們可以看到西瓜跟香蕉是絕配，在有限的重量限制下給我們最大的收益。我們來(lái)嘗試用算法把它描述出來(lái)。如我前面所說(shuō)，最簡(jiǎn)單的就是暴力遞歸，每次遇到一種水果，我們只有兩個(gè)選擇，要么在背包還放得下它的時(shí)候把它放進(jìn)去，要么就直接不放它，這樣就能幫我們列舉出所有的情形，然后我們只取收益最大的那種。

private int knapsackRecursive(int[] profits, int[] weights, int capacity, int currentIndex) {
        if (capacity <= 0 || currentIndex >= profits.length)
            return 0;

        // 在當(dāng)前元素可以被放進(jìn)背包的情況下遞歸的處理剩余元素
        int profit1 = 0;
        if( weights[currentIndex] <= capacity )
            profit1 = profits[currentIndex] + knapsackRecursive(profits, weights,
                    capacity - weights[currentIndex], currentIndex + 1);

        // 跳過(guò)當(dāng)前元素處理剩余元素
        int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);

        return Math.max(profit1, profit2);
    }

遞歸調(diào)用

我們可以畫(huà)一下遞歸調(diào)用的樹(shù)，由于重量跟收益數(shù)組是一成不變的，對(duì)我們的算法設(shè)計(jì)過(guò)程沒(méi)有影響，每次可能變化的只有剩余可用重量跟代表當(dāng)前處理到哪個(gè)元素的索引，從這張遞歸調(diào)用樹(shù)更加可以確定暴力遞歸數(shù)據(jù)越大時(shí)更耗時(shí)，同時(shí)也揭露了有些場(chǎng)景被多次重復(fù)計(jì)算。哈，這就輪到我們緩存大法出場(chǎng)了！由于只有重量跟索引在處理過(guò)程中變化，那我們可以用一個(gè)二維數(shù)組來(lái)存儲(chǔ)已經(jīng)計(jì)算的結(jié)果。這個(gè)過(guò)程不必詳述，直接上代碼：

private int knapsackRecursive(Integer[][] dp, int[] profits, int[] weights, int capacity,
                                  int currentIndex) {

        if (capacity <= 0 || currentIndex >= profits.length)
            return 0;

        // 如果已經(jīng)算得結(jié)果，直接返回
        if (dp[currentIndex][capacity] != null)
            return dp[currentIndex][capacity];

        // 在當(dāng)前元素可以被放進(jìn)背包的情況下遞歸的處理剩余元素
        int profit1 = 0;
        if (weights[currentIndex] <= capacity)
            profit1 = profits[currentIndex] + knapsackRecursive(dp, profits, weights,
                    capacity - weights[currentIndex], currentIndex + 1);

        // 跳過(guò)當(dāng)前元素處理剩余元素
        int profit2 = knapsackRecursive(dp, profits, weights, capacity, currentIndex + 1);

        dp[currentIndex][capacity] = Math.max(profit1, profit2);
        return dp[currentIndex][capacity];
    }

好啦，最終所有的結(jié)果都存儲(chǔ)在這個(gè)二維數(shù)組里面，我們可以確定我們不會(huì)有超過(guò)NC個(gè)子問(wèn)題，N是元素的數(shù)量，C是背包可容重量，也就是說(shuō)，到這兒我們時(shí)間空間復(fù)雜度都只有O(NC)了。

事情到這里還沒(méi)有結(jié)束，我們來(lái)嘗試用自下而上的方法來(lái)考慮這道題，來(lái)看看能不能獲得更優(yōu)解。本質(zhì)上，我們想在上面的遞歸過(guò)程中，對(duì)于每一個(gè)索引，每一個(gè)剩余的可容重量，我們都想在這一步獲得可以的最大收益。處理第3個(gè)元素時(shí)，我們想獲得能拿到的最大收益。處理第4個(gè)元素時(shí)，我們還是想獲得可以拿到的最大收益。(畢竟獲取最大利潤(rùn)是每個(gè)人的目標(biāo)嘛)dp[i][c]就代表從最開(kāi)始i=0時(shí)計(jì)算到當(dāng)前i的最大收益。那每次我們也只有兩種選擇：

1. 跳過(guò)當(dāng)前元素，那處理到這兒我們只能拿到前面過(guò)程中最大收益dp[i-1][c]。
2. 只要重量能放得下，放入這個(gè)元素，那么這時(shí)候的最大收益就為profit[i] + dp[i-1][c-weight[i]]。

最終我們想要獲得的最大收益就是這倆中的最大值。dp[i][c] = max (dp[i-1][c], profit[i] + dp[i-1][c-weight[i]])。

 public int solveKnapsack(int[] profits, int[] weights, int capacity) {
        if (capacity <= 0 || profits.length == 0 || weights.length != profits.length)
            return 0;

        int n = profits.length;
        int[][] dp = new int[n][capacity + 1];

        // 0空間就0收益
        for(int i=0; i < n; i++)
            dp[i][0] = 0;

        // 在處理第一個(gè)元素時(shí)，只要它重量可以被背包容下，那肯定放入比不放入收益高
        for(int c=0; c <= capacity; c++) {
            if(weights[0] <= c)
                dp[0][c] = profits[0];
        }

        // 循環(huán)處理所有元素所有重量
        for(int i=1; i < n; i++) {
            for(int c=1; c <= capacity; c++) {
                int profit1= 0, profit2 = 0;
                // 包含當(dāng)前元素
                if(weights[i] <= c)
                    profit1 = profits[i] + dp[i-1][c-weights[i]];
                // 不包含當(dāng)前元素
                profit2 = dp[i-1][c];
                // 取最大值
                dp[i][c] = Math.max(profit1, profit2);
            }
        }

        // dp的最后一個(gè)元素就是最大值
        return dp[n-1][capacity];
    }

這樣時(shí)間空間復(fù)雜度也都在O(N*C)。

那怎么找到選擇的元素呢？其實(shí)很簡(jiǎn)單，我們之前說(shuō)過(guò)，不選中當(dāng)前元素的話，當(dāng)前的最大收益就是處理前一個(gè)元素時(shí)的最大收益，換言之，只要在dp里的上下倆元素相同的，那那個(gè)索引所代表的元素肯定沒(méi)被選中，dp里第一個(gè)不同的總收益所在的位置就是選中的元素所在的位置。

private void printSelectedElements(int dp[][], int[] weights, int[] profits, int capacity) {
        System.out.print("Selected weights:");
        int totalProfit = dp[weights.length - 1][capacity];
        for (int i = weights.length - 1; i > 0; i--) {
            if (totalProfit != dp[i - 1][capacity]) {
                System.out.print(" " + weights[i]);
                capacity -= weights[i];
                totalProfit -= profits[i];
            }
        }

        if (totalProfit != 0)
            System.out.print(" " + weights[0]);
        System.out.println("");
    }

這個(gè)算法夠簡(jiǎn)單吧？但我覺(jué)得還是不能就這么結(jié)束了，我們大費(fèi)周章地?fù)Q了一種思路來(lái)解題，取得同樣的復(fù)雜度就結(jié)束了嗎，我們?cè)賮?lái)觀察下我們這個(gè)算法。我們發(fā)現(xiàn)我們?cè)谔幚懋?dāng)前元素時(shí)，我們需要的僅僅是在前一個(gè)元素時(shí)各個(gè)索引最大的收益，再往前的數(shù)據(jù)我們根本不關(guān)心，那這就是一個(gè)優(yōu)化的點(diǎn)，我們可以把dp的size大幅縮減。

static int solveKnapsack(int[] profits, int[] weights, int capacity) {
        if (capacity <= 0 || profits.length == 0 || weights.length != profits.length)
            return 0;

        int n = profits.length;
        // 我們只需要前面一次的結(jié)果來(lái)獲得最優(yōu)解，因此我們可以把數(shù)組縮減成兩行
        // 我們用 `i%2` 代替`i` 跟 `(i-1)%2` 代替`i-1`
        int[][] dp = new int[2][capacity+1];

        // 在處理第一個(gè)元素時(shí)，只要它重量可以被背包容下，那肯定放入比不放入收益高
        for(int c=0; c <= capacity; c++) {
            if(weights[0] <= c)
                dp[0][c] = dp[1][c] = profits[0];
        }

        // 循環(huán)處理所有元素所有重量
        for(int i=1; i < n; i++) {
            for(int c=0; c <= capacity; c++) {
                int profit1= 0, profit2 = 0;
                // 包含當(dāng)前元素
                if(weights[i] <= c)
                    profit1 = profits[i] + dp[(i-1)%2][c-weights[i]];
                // 不包含當(dāng)前元素
                profit2 = dp[(i-1)%2][c];
                // 取最大值
                dp[i%2][c] = Math.max(profit1, profit2);
            }
        }

        return dp[(n-1)%2][capacity];
    }

這時(shí)候空間復(fù)雜度就只剩下O(N)了，嘿嘿，這是比較讓人滿(mǎn)意的結(jié)果了。不過(guò)要是同學(xué)們?cè)賳市牟】褚稽c(diǎn)，再變態(tài)一點(diǎn)，再觀察一下我們的算法，可以發(fā)現(xiàn)其實(shí)我們只需要前面一次結(jié)果中的兩個(gè)值dp[c] 跟 dp[c-weight[i]]。那我們可不可以把結(jié)果都放在一個(gè)一維數(shù)組里面，來(lái)看看：

1. 當(dāng)我們?cè)L問(wèn)dp[i]的時(shí)候，它還沒(méi)被當(dāng)前迭代的結(jié)果覆蓋掉，可用！
2. 當(dāng)我們?cè)L問(wèn)dp[c-weight[i]]的時(shí)候，如果weight[i]>0，那么dp[c-weight[i]]是有可能已經(jīng)被覆蓋掉了。

這并不是什么難題，只要我們改變處理順序就好了：c:capacity-->0。從后往前處理，就能保證我們?cè)谛薷膁p里面任何值得時(shí)候，這個(gè)被修改的值都用不到了，大家想想，是不是這么個(gè)道理。
思路想明白了，那手寫(xiě)代碼就很簡(jiǎn)單了：

static int solveKnapsack(int[] profits, int[] weights, int capacity) {
        if (capacity == 0 || profits.length == 0 || weights.length != profits.length) {
            return 0;
        }
        int n = profits.length;
        int[] dp = new int[capacity + 1];
        for (int i = 1; i <= capacity; i++) {
            if (weights[0] <= i) {
                dp[i] = profits[0];
            }
        }
        for (int j = 1; j < n; j++) {
            for (int c = capacity; c >= 0; c--) {
                int profit1 = 0;
                if (weights[j] <= c) {
                    profit1 = profits[j] + dp[c - weights[j]];
                }
                int profit2 = dp[c];
                dp[c] = Math.max(profit1, profit2);
            }
        }
        return dp[capacity];
    }

現(xiàn)在我們的算法可以說(shuō)是最優(yōu)咯！最后大家再來(lái)好好地總結(jié)下，其實(shí)動(dòng)態(tài)規(guī)劃就是想辦法減少不必要的內(nèi)存消耗，跟復(fù)用之前問(wèn)題的結(jié)果來(lái)解決現(xiàn)在的問(wèn)題以用最少的時(shí)間解決問(wèn)題。思路就是這么簡(jiǎn)單，但是關(guān)于內(nèi)存優(yōu)化，這就得靠經(jīng)驗(yàn)的積累了，大家多加練習(xí)做手熟了就好啦。