题解 | #01背包#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        // write code here
        vector<vector<int>> dp(n,vector<int>(V+1,0));
        for (int j= vw[0][0]; j < V+1; j++) {
            dp[0][j] = vw[0][1]; 
        }

        for (int i=1; i<n; i++) {
            for (int j=0; j<=V; j++) {
                if (vw[i][0] > j) {
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-vw[i][0]]+vw[i][1]);
                }
                // std::cout<<"dp["<< i <<"]["<<j<<"] =" <<dp[i][j]<<endl;
            }
        }

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

01背包问题

状态转移方程： 

`dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);`

初始化

可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

遍历顺序

先遍历物品，然后遍历背包

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}