题解 | 完全背包

class Solution {
public:
    vector<int> knapsack(int v, int n, vector<vector<int> >& nums) {
        //v背包体积, n是多少种物品, 物品体积和价值
        //采用动态规划，体积从0到V更新，前i种物品最大价值是多少（能否满足），
        vector<int> res;
        vector<vector<int>> dp( n+1, vector<int>(v+1, 0) );

        for(int i=1; i <= n; i++){
            for(int j=0; j<=v ;++j){
                dp[i][j] = dp[i-1][j];  //先初始化其不使用此物品的价值情况，因为可能此物品放不下，但是也是有价值的；
                //当背包容量可以放下此物品时，
                if(j >= nums[i-1][0])
                    dp[i][j] = max( dp[i][j], dp[i][j-nums[i-1][0]]+nums[i-1][1] );
            }
        }
        res.push_back(dp[n][v]);



        dp = vector<vector<int>>(n+1, vector<int>(v+1, -1));//大于等于0都表示可以装满，所以用-1表示装不满
        //应该进行重新赋值，使用resize的话，原来的数不会改变，只有在增加容量的时候新的空间赋值成新数；可以使用assign();
        //dp.resize(n+1, vector<int>(v+1, -1));  //-1表示默认是不能组装
        dp[0][0] = 0;

        for(int i=1; i<=n; ++i){
            int vi = nums[i-1][0], wi = nums[i-1][1]; 
            for(int j=0; j<=v; ++j){
                dp[i][j] = dp[i-1][j]; //基础情况；

                if(j >= vi && dp[i][j-vi] != -1){
                    dp[i][j] = max( dp[i][j], dp[i][j-vi] + wi );
                }
            }
        }
        int exact = dp[n][v];
        res.push_back(exact == -1? 0:exact);

        return res;
    }
};