题意整理：

0-1背包是极其经典的动态规划问题。理清题意，题目通过数组给出 个背包，每个背包为二元数对 ，求解对给定体积 ，在选择若干个物品 ，满足时能够得到的最大重量。

方法一：动态规划

核心思想：

可以发现，对一个物体，我们可以选择将它装入背包，以及不选择，这就将问题划分成了更小的子问题，可以利用动态规划求解。
令 表示当前分析到第 个物品，背包体积为 时能够得到的最大质量和。
容易得到，方程的转移为
其中边界条件为 ,既没有选择任何物品，或背包容量为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));
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= V; ++j) {
                dp[i][j] = dp[i - 1][j];//不装入物品
                if(j >= vw[i - 1][0]) {//体积足够，可以装入
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);
                }
            }
        }
        return dp[n][V];
    }
};

复杂度分析：

时间复杂度：,即为两重循环的开销
空间复杂度：,即为dp数组使用的空间

方法二：空间优化的动态规划

核心思想：

观察dp方程式，以及方法一的代码可以发现，每次对于 的选择都只与第 层相关，所以可以采用滚动数组的思想，优化空间。注意到为了避免答案被覆盖，此时需要从后往前枚举体积。

核心代码：

class Solution {
public:
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        vector<int> dp(V + 1);//滚动数组
        for(int i = 1; i <= n; ++i) {
            for(int j = V; j > 0; --j) {
                if(j >= vw[i - 1][0]) {//体积足够，可以装入
                    dp[j] = max(dp[j], dp[j - vw[i - 1][0]] + vw[i - 1][1]);
                } // else dp[j] = dp[j]
                //不能装入时数组大小保持原样即可
            }
        }
        return dp[V];
    }
};

复杂度分析：

时间复杂度：,即为两重循环的开销
空间复杂度：,即为dp数组使用的空间，此时为一维的数组，开销只和体积有关。