题解 | #01背包#

int knapsack(int V, int n, vector<vector<int> >& vw) {
    //状态矩阵，表示从i个物品中选取，背包容量为j时的最大重量
    //明确状态矩阵的含义，下标的含义十分重要。。。
    //这里面就有初始化了。直接将左边界和上边界赋值为0，这就是初始化
    vector<vector<int>> dp(n+1,vector<int>(V+1));
    //循环计算状态矩阵中的每一个值
    for(int i=1;i<=n;i++){
        for(int j=1;j<=V;j++){
            //判断此时是否能选择物品i的条件
            //当背包容量小于等于物品i的体积时，表明此时可以选择物品i，
            //但是这时还是需要考虑是否选择物品i
            //1、物品i不放置，则此时dp[i][j]就等于前i-1个物品装入背包容量为j的最大重量也就是dp[i-1][j]
            //2、物品i放置，则需要考虑背包容量j去除物品i的体积，
            //    剩余的体积装入前i-1个物品的最大重量（注意此时物品i已经选择,只能从前i-1个物品中进行选择。
            //    此时的重量为前i-1个物品装入当前容量j去除物品i的体积剩余体积的最大重量dp[i-1][j-vw[i-1][0]]
            //    在加上物品i的重量
            //将1和2取最大值就是当前物品的最大值。
            if(vw[i-1][0]<=j){
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-vw[i-1][0]]+vw[i-1][1]);
            }
            //当vw[i-1][0]>j时，无法选择物品i，只能选择从前i-1个物品中选取
            //此时dp[i][j]就等于前i-1个物品装入背包容量为j的最大重量也就是dp[i-1][j]
            else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    return dp[n][V];    
}