题解 | 01背包

    class Solution {
    public:
        int knapsack(int V, int n, vector<vector<int> >& vw) {
            vector<vector<int>> dp(n+1, vector<int>(V+1));  
            //dp[i][j] 表示::从i个物品选取,背包容量为j的最大重量;
            for(int i=1; i<=n; i++){
                for(int j=1; j<=V;++j){
                    if( vw[i-1][0] <= j){  //第i物品的体积小于j体积,考虑是否放入,不放入则继承dp[i-1][j],放入则继承dp[i-1][i-vw[i-1][1]]
                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-vw[i-1][0]]+vw[i-1][1] );
                    }else{   //物品i的体积大于j背包
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }

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