昨天詳解了一下背包問題，之后有人問我如果每種元素都可以選擇任意數(shù)目那會怎么樣？這是很常見的背包問題的變種問題，只需要我們在原來的算法基礎(chǔ)上做一點小小的改動，我們一起來看下。

照例來看下題目定義：給定N種水果的重量跟收益，我們需要把它們放進一個可容重量為C的背包里，使得包里的水果在總重量不超過C的同時擁有最高的收益，假設(shè)水果數(shù)量無限，一種可選多個。

這次我們還要去賣水果，在攜帶量有限的情況下獲得最大的收益。假設(shè)檔情況是：
水果: { 蘋果, 橙子, 西瓜 }
重量: { 1, 2, 3 }
收益: { 15, 20, 50 }
可容重量: 5。

我們也同樣先來稍稍列舉下可能的情況：
5 蘋果 (總重 5) => 75 收益
1 蘋果 + 2 橙子 (總重 5) => 55 收益
2 蘋果 + 1 西瓜 (總重 5) => 80 收益
1 橙子 + 1 西瓜 (總重5) => 70 收益。

我們可以看到兩個蘋果跟西瓜是絕配，載重量有限的情況下我們獲得了最大收益。關(guān)鍵是我們得把這個過程通過代碼表達出來，我們來分析一下，對于每種水果，我們可以選擇放進去然后進行下一輪選擇，或者不放進去直接進行下一輪選擇，在每次放進去一種水果A之后，我們還要選擇要不要把A再放進去，知道超出背包的載重量，然后在這個過程中我們要選出兩種選擇中帶來最大收益的那個。

也照舊，我們先用遞歸來把算法實現(xiàn)出來，后期再慢慢優(yōu)化。上面已經(jīng)描述得很清楚了，我們可以直接寫出來：

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

        // 選擇了當前元素之后繼續(xù)循環(huán)處理，要注意這里選擇結(jié)束后并沒有把索引+1
        int profit1 = 0;
        if (weights[currentIndex] <= capacity)
            profit1 = profits[currentIndex]
                    + knapsackRecursive(profits, weights, capacity - weights[currentIndex], currentIndex);

        // 跳過當前元素然后繼續(xù)做選擇
        int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);

        return Math.max(profit1, profit2);
    }

想必大家都看的出來，我們的算法跟昨天的很相似，除了一些條件的變化。要注意的是這里的時間復(fù)雜度變成了O(2^(N+C))，N是元素元素數(shù)量，C是背包最大載重，因為我們可以重復(fù)選擇某一元素。

現(xiàn)在遇到這種問題，寫出了暴力遞歸的做法，大家肯定都能條件反射般地用緩存來優(yōu)化算法了。這邊已經(jīng)不需要我賣關(guān)子了，咱們直接上代碼：

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

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

        // 檢查我們之前有木有遇到過同樣的子問題，有就直接返回結(jié)果
        if (dp[currentIndex][capacity] == null) {
            // 做完選擇之后繼續(xù)遞歸處理，注意選擇后我們還可以繼續(xù)選擇當前元素
            int profit1 = 0;
            if (weights[currentIndex] <= capacity)
                profit1 = profits[currentIndex] + knapsackRecursive(dp, profits, weights,
                        capacity - weights[currentIndex], currentIndex);

            // 跳過當前元素直接進行下一次遞歸
            int profit2 = knapsackRecursive(dp, profits, weights, capacity, currentIndex + 1);

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

這時候因為我們把子問題的結(jié)果都緩存在二維數(shù)組中，所以我們最多進行了NC次計算，所以我們的時間復(fù)雜度下降到了O(NC)，但是現(xiàn)在想必大家也都能發(fā)現(xiàn)都發(fā)覺了通常光緩存是達不到最優(yōu)的，那我們再來試試從另一個方向，采用自下而上的方式來思考這個問題。（又到了激動人心的環(huán)節(jié)了!）

本質(zhì)上，我們還是想在上面的遞歸過程中，對于每一個索引，每一個剩余的可容重量，我們都想在這一步獲得可以的最大收益。我們還是面臨兩個選擇，

1. 跳過當前元素，那么我們這時候的最大收益肯定跟前面一個元素的最大收益相同，即dp[index-1][c]。
2. 選擇當前元素，那么我們的最大收益就是當前元素的收益加上剩余載重量可得的最大收益，即profit[index] + dp[index][c-weight[index]]。

最后我們得到了想獲得最大收益的公式：dp[index][c] = max (dp[index-1][c], profit[index] + dp[index][c-weight[index]])。跟我們昨天的思路簡直一毛一樣！

剛看完昨天文章的大家肯定明白是怎么回事了，我也不多說了，直接把代碼貼出來供大家觀賞：

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;

        // 循環(huán)處理所有元素所有重量
        for (int i = 0; i < n; i++) {
            for (int c = 1; c <= capacity; c++) {
                int profit1 = 0, profit2 = 0;
                if (weights[i] <= c)
                    profit1 = profits[i] + dp[i][c - weights[i]];
                if (i > 0)
                    profit2 = dp[i - 1][c];
                dp[i][c] = profit1 > profit2 ? profit1 : profit2;
            }
        }

        // 最大收益肯定出現(xiàn)在最右下角
        return dp[n - 1][capacity];
    }

發(fā)現(xiàn)沒有，這個問題對我們根本毫無壓力？掌握了昨天的進階文章，我們甚至還可以對這個算法再進行優(yōu)化兩百遍！(其實兩遍)

皮這一下真開心，最后的優(yōu)化我就不帶大家一起走了，思路都是一樣的，留給大家去思考，大家平時做算法題的時候一定要多思考，盡力把題目轉(zhuǎn)化成我們熟悉的題目，轉(zhuǎn)換成功后那我們結(jié)題呀優(yōu)化呀一切都游刃有余了。