题解 | #01背包#

#include <vector>
class Solution {
public:

    int knapsack(int V, int n, vector<vector<int> >& vw) {
        // 首先，先创建一个二维数组，dp【i】【j】 表示前i个物品所能使得容量为j的背包的重量的最大值
        vector<vector<int>> dp(n+1, vector<int>(V + 1));
        if(V == 0 || n == 0) return 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= V; j++){//j表示背包的容量
                if(j < vw[i - 1][0]) dp[i][j] = dp[i - 1][j];//当当前的背包容量小于第i个物品的体重，就直接不加入第i物品
                else{
                    dp[i][j] = max(dp[i - 1][j - vw[i -1][0]] + vw[i - 1][1], dp[i - 1][j]);
                }//这个表示当取第i个物品时，以为背包的容量没那么大了，你要找背包容量减去第i个物品的容量所能容纳的最大重量也就是dp[i - 1][j - vm[i - 1][1]] 后面的这个vm[i - 1][1]表示的是第i个物品的重量

            }
        }
        return dp[n][V];
    }
};