题目的主要信息：

• 背包体积固定为V，从所有物品中选择几件物品，加起来体积不超过V，使加起来质量最大。
• 所有数据大于0，无特殊情况

方法一：递归（超时）

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

• $x_{i}x\_i$为1或0，表示对于物品$ii$取或者不取，$v_{i}v\_i$表示物品$ii$的体积，$w_{i}w\_i$表示物品$ii$的质量，$nn$是物品总数，$VV$是背包总体积
• 问题求：$max(x_1\ast w_1+x_2\ast w_2+\mathrm{.}\mathrm{.}\mathrm{.}+x_n\ast w_n)max(x\_1*w\_1+x\_2*w\_2+...+x\_\{n\}*w\_\{n\})$
• 限定条件为：

对于$(n,V)(n,V)$的问题，如果最后一个物品$nn$超出了体积限制不能选，那么该问题就变成了$(n-1,V)(n-1,V)$的子问题；如果可以选，那么我们要选取$(n-1,V)(n-1,V)$和$(n-1,V-v_n)+w_n(n-1,V-v\_n)+w\_n$之间的最大值。

具体做法：

按照上述思路，我们可以用递归解决，写一个递归函数计算对于$nn$个物品，$VV$的容量，返回最大的质量，其中递归回溯条件为剩余容量为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);  //送入最大下标
    }
};

复杂度分析：

• 时间复杂度：$O(2^n)O(2^n)$，最坏情况为树型递归，$T(n)=2T(n-1)+1T(n)=2T(n-1)\; +\; 1$
• 空间复杂度：$O(n)O(n)$，递归树最大深度

方法二：动态规划

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

具体做法：

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

依照方法一的思路，如果这时候容量不够撞入这件物品，则$dp[i][j]=dp[i-1][j]dp[i][j]\; =\; dp[i\; -\; 1][j]$，若是能够装入则$dp[i][j]=max(dp[i-1][j],dp[i-1][j-vw[i-1][0]]+vw[i-1][1])dp[i][j]\; =\; max(dp[i\; -\; 1][j],\; dp[i\; -\; 1][j\; -\; vw[i\; -\; 1][0]]\; +\; vw[i\; -\; 1][1])$，因为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];
    }
};

复杂度分析：

• 时间复杂度：$O(nV)O(nV)$，遍历辅助数组的复杂度
• 空间复杂度：$O(nV)O(nV)$，辅助数组dp