题解 | #01背包#

说实话背包有点乱

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) {
      //  dp[i] 表示容量为i时所能容纳的最大重量
      std::vector<int> dp(V + 1, 0);
      
      //  装包针对每件物品，选择是否装入
      for (int i = 1; i <= n; ++i) {
        //  空包时装下去，跟已经装了东西的状态有关联，所以倒序使用
        //  容量更大才是之前的状态！！
        //  从后往前
        for (int j = V; j >= 1; --j) {
          if (j >= vw[i - 1][0]) {
            dp[j] = std::max(dp[j - vw[i - 1][0]] + vw[i - 1][1], dp[j]);
          }
        }
      }
      
      return dp[V];
    }
};