牛客网：NC309 完全背包

题目

你有一个背包，最多能容纳的体积是 V。
现在有 n 种物品，每种物品有任意多个，第 i 种物品的体积为 [中等] NC309 完全背包 - 图1 ，价值为 [中等] NC309 完全背包 - 图2 。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？

示例：

输入：6,2,[[5,10],[3,1]]
输出：[10,2]

输入：8,3,[[3,10],[9,1],[10,1]]
输出：[20,0]
说明：无法恰好装满背包。

输入：13,6,[[13,189],[17,360],[19,870],[14,184],[6,298],[16,242]]
输出：[596,189]
说明：可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189.

解答 & 代码

解法一：二维 dp

问题一：求这个背包至多能装多大价值的物品？求 dp[n][v]

动态规划数组 **dp**：dp[i][j] 代表只从前 i 个物品 [0...i-1] 中取，背包容量 j，可以装的物品的最大价值
状态转移方程：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vi] + wi)，即考虑两种情况的最大值：
- 不把第 i 个物品 vi 放入背包，显然最大价值 = dp[i - 1][j]
- 把第 i 个物品 vi 放入背包，显然最大价值 = dp**[i]**[j - vi] + wi，当然这种 case 的前提是 j - vi >= 0
  - 完全背包问题和 01 背包问题的区别就在于，01 背包每个物品只能取一次，但是完全背包每个物品能取多次。因此取了物品 i 后，物品 i 还能再取，因此这里是 dp**[i]**[j - vi] + wi 而不是 dp**[i - 1]**[j - vi] + wi
初始化：
- dp[0][j] = 0，可用的物品数为 0，则背包能装的最大价值只能为 0
- dp[i][0] = 0，背包体积为 0，则不能装任何东西，最大价值也只能为 0
- **dp** 数组其它所有位置 **dp[i][j]** 都初始化为 **0**

问题二：若背包恰好装满，求至多能装多大价值的物品？求 max(0, dp[n][v])

动态规划数组 **dp**：dp[i][j] 代表只从前 i 个物品 [0...i-1] 中取，背包容量 j，恰好装满背包的物品的最大价值
状态转移方程：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vi] + wi)，即考虑两种情况的最大值：
- 不把第 i 个物品 vi 放入背包，显然最大价值 = dp[i - 1][j]
- 把第 i 个物品 vi 放入背包，显然最大价值 = dp**[i]**[j - vi] + wi，当然这种 case 的前提是 j - vi >= 0
  
  以上状态转移同问题一，唯一的区别就在于初始化，恰好装满背包要将 **dp** 数组所有位置初始化为 **INT_MIN**，**dp[i][0]** 初始化为 **0**。最终如果 dp[n][v] < 0，说明无法恰好装满背包，则最大价值物品为 0

初始化：

dp[0][j] = INT_MIN，可用的物品数为 0，除非背包为 0（dp[0][0]=0），否则其它容量都不可能装满，因此都设为 INT_MIN，使得取 max 时不会被取到
dp[i][0] = 0，背包体积为 0，则不装任何东西恰好装满，最大价值为 0

**dp** 数组其它所有位置 **dp[i][j]** 都初始化为 **INT_MIN**，最终如果 **dp[i][j] < 0**，则说明从 **i** 个物品取，不能恰好装满容量为 **j** 的背包

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 
* @param v int整型 
* @param n int整型 
* @param nums int整型vector<vector<>> 
* @return int整型vector
*/
vector<int> knapsack(int v, int n, vector<vector<int> >& nums) {
   vector<vector<int>> dp1(n + 1, vector<int>(v + 1, 0));
   vector<vector<int>> dp2(n + 1, vector<int>(v + 1, INT_MIN));
   for(int i = 0; i <= n; ++i)
       dp2[i][0] = 0;
   for(int i = 1; i <= n; ++i)
   {
       int vi = nums[i - 1][0];
       int wi = nums[i - 1][1];
       for(int j = 1; j <= v; ++j)
       {
           if(j - vi >= 0)
           {
               dp1[i][j] = max(dp1[i - 1][j], dp1[i][j - vi] + wi);
               dp2[i][j] = max(dp2[i - 1][j], dp2[i][j - vi] + wi);
           }
           else
           {
               dp1[i][j] = dp1[i - 1][j];
               dp2[i][j] = dp2[i - 1][j];
           }
       }
   }

   vector<int> result(2);
   result[0] = dp1[n][v];
   result[1] = dp2[n][v] < 0 ? 0 : dp2[n][v];
   return result;
}
};

复杂度分析：n 个物品，背包容量 v

时间复杂度 O(nv)：
空间复杂度 O(nv)：

执行结果：

执行结果：通过

执行用时：15 ms, 在所有 C++ 提交中击败了 44.45% 的用户
内存消耗：8.064 MB, 在所有 C++ 提交中击败了 43.75% 的用户

解法二：状态压缩一维 dp

二维状态 dp[i][j] 只和前一行的状态 dp[i - 1][j]、dp[i][j - vi] 有关，因此可以压缩为一维 dp 数组
注意区别：

恰好装满和不恰好装满的区别：
1. 恰好装满的情况要将 **dp** 数组全部初始化为 **INT_MIN**，**dp[0] = 0**；
2. 不用恰好装满则将 dp 数组全部初始化为 0
完全背包和 01 背包的区别：
1. 01 背包内循环要逆序遍历，因为 01 背包 dp[j]（即本来的 dp[i][j]）和上一行左边的状态 dp[**i - 1]**[j - vi] 有关，压缩为一行 dp 数组时，如果 j 正序遍历，那么前面的 dp[j - vi] 的状态已被更新为第 i 行的，而不是第 i - 1 行的了，因此要逆序遍历
2. 本题完全背包内循环必须正序遍历，因为完全背包 dp[j]（即本来的 dp[i][j]）和本行左边的状态 dp[**i**][j - vi] 有关，压缩为一行 dp 数组时，j 正序遍历，前面的 dp[j - vi] 的状态才会被更新为第 i 行的，否则还是第 i - 1 行的状态，因此要正序遍历

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param v int整型 
     * @param n int整型 
     * @param nums int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> knapsack(int v, int n, vector<vector<int> >& nums) {
        vector<int> dp1(v + 1, 0);
        vector<int> dp2(v + 1, INT_MIN);
        dp2[0] = 0;
        for(int i = 1; i <= n; ++i)
        {
            int vi = nums[i - 1][0];
            int wi = nums[i - 1][1];
            // 注意这里是正序！
            for(int j = vi; j <= v; ++j)
            {
                dp1[j] = max(dp1[j], dp1[j - vi] + wi);
                dp2[j] = max(dp2[j], dp2[j - vi] + wi);
            }
        }

        vector<int> result(2);
        result[0] = dp1[v];
        result[1] = dp2[v] < 0 ? 0 : dp2[v];
        return result;
    }
};

复杂度分析：n 个物品，背包容量 v

时间复杂度 O(nv)：
空间复杂度 O(v)：

执行结果：

执行结果：通过

执行用时：6 ms, 在所有 C++ 提交中击败了 70.83% 的用户
内存消耗：0.468 MB, 在所有 C++ 提交中击败了 95.83% 的用户

[中等] NC309 完全背包

题目

解答 & 代码

解法一：二维 dp

解法二：状态压缩 一维 dp

解法二：状态压缩一维 dp