算法分享之01背包问题

01背包问题是最简单的背包问题，一般形式是问一共有件物品，第件物品的重量为，价值为，问在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？这类问题可以自顶向下分解为子问题，也可以直接子问题相加，因此可以考虑递归或者动态规划。

牛客网上的01背包问题可以参考01背包 、购物单 、牛能和牛可乐的礼物 等问题，我们考虑的最简单的01背包题解可以具体参考这篇题解 。

方法一：递归

递归是一种分治法，我们可以如下考虑：

• 为1或0，表示对于物品取或者不取，表示物品的体积，表示物品的质量，是物品总数，是背包总体积
• 问题求：
• 限定条件为：

对于的问题，如果最后一个物品超出了体积限制不能选，那么该问题就变成了的子问题；如果可以选，那么我们要选取和之间的最大值。

按照上述思路，我们可以用递归解决，写一个递归函数计算对于个物品，的容量，返回最大的质量，其中递归回溯条件为剩余容量为0或者物品考虑完了。

class Solution {
public:
    vector<vector<int> > VW;
    int recursion(int n, int capacity){
        if (n < 0 || capacity == 0){
            // 初始条件
            return 0;
        } else if(VW[n][0] > capacity){
            // 装不下该珠宝
            return recursion(n - 1, capacity);
        } else {
            // 可以装下的情况
            int temp1 = recursion(n - 1, capacity); //装
            int temp2 = recursion(n - 1, capacity - VW[n][0]) + VW[n][1]; //不装
            return max(temp1, temp2);
        }
        return 0;
    }
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        VW = vw;
        return recursion(n - 1, V);  //送入最大下标
    }
};

方法二：动态规划

方法一的递归是一种自顶向下的计算，从代码中就可见很多重复的运算，因此我们可以采用动态规划自底向上直接相加，避免多余的运算。

建立一个二维数组dp，表示在第件物品时，还有的容量时，能装入的最大质量。

依照方法一的思路，如果这时候容量不够撞入这件物品，则，若是能够装入则，因为dp下标从1开始，vw下标从0开始，所以vw要减1，dp所有下标为0的行或者列置为0。

class Solution {
public:
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        vector<vector<int> > dp(n + 1, vector<int>(V + 1, 0));// 全部初始化为0
        for(int i = 1; i <= n; i++){
            //依照dp表，dp最前一列最前一行都是0，从下标1开始算，但是vw从0开始，需要减一
            for(int j = 1; j <= V; j++){  
                if(j < vw[i - 1][0]) //容量不够
                    dp[i][j] = dp[i - 1][j]; 
                else{
                    //选择大的
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);
                }
            }
        }
        return dp[n][V];
    }
};