题解 | #完全背包#

class Solution {
public:
    vector<int> knapsack(int v, int n, vector<vector<int> >& nums) {
        vector<int> res;//结果
        vector<int> dp(v+1,0);//可不必装满时的最大价值
        vector<int> p(v+1,-0xff);//必须装满的价值最大,-0xff无穷小，设置-0xff原因：任何数加一个无穷小都是无穷小，有阻断作用。意味着当顺向滚动时，拿当前物品后还剩余空间而剩余空间不能被装满的话当前容量也无法被装满
        p[0]=0;//容量为0时可以理解为装满，而又没放物品，价值为0
  
        /*1.继承0/1背包滚动方法，求完全背包最大价值*/
        // for(int i = 0;i < n;i++)//逆向滚动
        //     for(int j = v;j > 0;j--)
        //         for(int k = 0;k <= j/nums[i][0];k++)
        //         {    
        //               dp[j] = max(dp[j]，k*nums[i][1] + dp[j-k*nums[i][0]]);
        //         }

        /*2.用0/1背包打表方法，发现下一层数据不用考虑上一层的数据，直接利用同一层前面的数据。*/
        for(int i = 0;i < n;i++)
            for(int j = nums[i][0];j <= v;j++)//顺向，能拿多少个相同物品，是前面的一个积累。如：背包大小6，物品大小3，大小3时可以放一个。大小6时，能先放一个，后还剩3容量，又前面知道大小3时可以放一个。所以现在能放下2个。
            {
                dp[j] = max(dp[j],dp[j-nums[i][0]] + nums[i][1]);//完全背包最大价值
                p[j] = max(p[j],p[j-nums[i][0]] + nums[i][1]);//j-nums[i][0]=0时，对应的p[j]才有有效值
            }

        if(p[v] < 0)
            res = {dp[v],0};
        else
            res = {dp[v],p[v]};;
        return res;
    }
};