关于背包问题的一点发散

昨天详解了一下背包问题，之后有人问我如果每种元素都可以选择任意数目那会怎么样？这是很常见的背包问题的变种问题，只需要我们在原来的算法基础上做一点小小的改动，我们一起来看下。

照例来看下题目定义：给定N种水果的重量跟收益，我们需要把它们放进一个可容重量为C的背包里，使得包里的水果在总重量不超过C的同时拥有最高的收益，假设水果数量无限，一种可选多个。

这次我们还要去卖水果，在携带量有限的情况下获得最大的收益。假设档情况是： 水果: { 苹果, 橙子, 西瓜 } 重量: { 1, 2, 3 } 收益: { 15, 20, 50 } 可容重量: 5。

我们也同样先来稍稍列举下可能的情况： 5 苹果 (总重 5) => 75 收益 1 苹果 + 2 橙子 (总重 5) => 55 收益 2 苹果 + 1 西瓜 (总重 5) => 80 收益 1 橙子 + 1 西瓜 (总重5) => 70 收益。

我们可以看到两个苹果跟西瓜是绝配，载重量有限的情况下我们获得了最大收益。关键是我们得把这个过程通过代码表达出来，我们来分析一下，对于每种水果，我们可以选择放进去然后进行下一轮选择，或者不放进去直接进行下一轮选择，在每次放进去一种水果A之后，我们还要选择要不要把A再放进去，知道超出背包的载重量，然后在这个过程中我们要选出两种选择中带来最大收益的那个。

也照旧，我们先用递归来把算法实现出来，后期再慢慢优化。上面已经描述得很清楚了，我们可以直接写出来：

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;

        // 选择了当前元素之后继续循环处理，要注意这里选择结束后并没有把索引+1
        int profit1 = 0;
        if (weights[currentIndex] <= capacity)
            profit1 = profits[currentIndex]
                    + knapsackRecursive(profits, weights, capacity - weights[currentIndex], currentIndex);

        // 跳过当前元素然后继续做选择
        int profit2 = knapsackRecursive(profits, weights, capacity, currentIndex + 1);

        return Math.max(profit1, profit2);
    }

想必大家都看的出来，我们的算法跟昨天的很相似，除了一些条件的变化。要注意的是这里的时间复杂度变成了O(2^(N+C))，N是元素元素数量，C是背包最大载重，因为我们可以重复选择某一元素。

现在遇到这种问题，写出了暴力递归的做法，大家肯定都能条件反射般地用缓存来优化算法了。这边已经不需要我卖关子了，咱们直接上代码：

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;

        // 检查我们之前有木有遇到过同样的子问题，有就直接返回结果
        if (dp[currentIndex][capacity] == null) {
            // 做完选择之后继续递归处理，注意选择后我们还可以继续选择当前元素
            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];
    }

这时候因为我们把子问题的结果都缓存在二维数组中，所以我们最多进行了NC次计算，所以我们的时间复杂度下降到了O(NC)，但是现在想必大家也都能发现都发觉了通常光缓存是达不到最优的，那我们再来试试从另一个方向，采用自下而上的方式来思考这个问题。（又到了激动人心的环节了!）

本质上，我们还是想在上面的递归过程中，对于每一个索引，每一个剩余的可容重量，我们都想在这一步获得可以的最大收益。我们还是面临两个选择，

跳过当前元素，那么我们这时候的最大收益肯定跟前面一个元素的最大收益相同，即dp[index-1][c]。
选择当前元素，那么我们的最大收益就是当前元素的收益加上剩余载重量可得的最大收益，即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;

        // 循环处理所有元素所有重量
        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;
            }
        }

        // 最大收益肯定出现在最右下角
        return dp[n - 1][capacity];
    }

发现没有，这个问题对我们根本毫无压力？掌握了昨天的进阶文章，我们甚至还可以对这个算法再进行优化两百遍！(其实两遍)

皮这一下真开心，最后的优化我就不带大家一起走了，思路都是一样的，留给大家去思考，大家平时做算法题的时候一定要多思考，尽力把题目转化成我们熟悉的题目，转换成功后那我们结题呀优化呀一切都游刃有余了。