每日OJ题_其它背包问题②_力扣879. 盈利计划（二维费用01背包）

目录

力扣879. 盈利计划

解析代码

代码优化

力扣879. 盈利计划

879. 盈利计划

难度 困难

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。

第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。

工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。

有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。

示例 1：

输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。

示例 2：

输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
输出：7
解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

提示：

• 1 <= n <= 100
• 0 <= minProfit <= 100
• 1 <= group.length <= 100
• 1 <= group[i] <= 100
• profit.length == group.length
• 0 <= profit[i] <= 100

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        
    }
};

解析代码

        题目结合例子多读几遍，就会发现是一个经典二维费用的背包问题。因此可以仿照二维费用的背包问题来定义状态表示。

状态表示：dp[i][j][k] 表示：从前 i 个计划中挑选，总人数不超过 j ，总利润至少为 k ，一共有多少种选法。

        这道题里面出现了一个至少，和我们之前做过的背包问题不一样。因此在分析状态转移程的时候要结合实际情况考虑一下。

状态转移方程：

        线性 dp 状态转移方程分析方式，一般都是根据最后一步的状况，来分情况讨论。结合题目的要求，我们有选择最后一个元素或者不选择最后一个元素两种策略：

• 不选 i 位置的计划：那我们只能去前 i - 1 个计划中挑选，总人数不超过 j ，总利润至少为 k 。此时一共有 dp[i - 1][j][k] 种选法 。
• 选择 i 位置的计划：那我们在前 i - 1 个计划中挑选的时候，限制就变成了，总人数不超过 j - g[i] ，总利润至少为 k - p[i] 。此时一共有 dp[i - 1][j - g[i]] [k - p[i]] 。

第二种情况下有两个细节需要注意：

1. j - g[i] < 0 ：此时说明 g[i] 过大，也就是人数过多。因为我们的状态表示要 求人数是不能超过 j 的，因此这个状态是不合法的，需要舍去。
2. k - p[i] < 0 ：此时说明 p[i] 过大，也就是利润太高。但是利润高正是我 们想要的。所以这个状态不能舍去。但是问题来了，我们的 dp 表是没有负数的下标的，这就意味着这些状态我们无法表示。其实根本不需要负的下标，根据实际情况来看，如果这个任务的利润已经能够达标了，我们仅需在之前的任务中，挑选出 来的利润⾄至少为 0 就可以了。因为实际情况不允许我们是负利润，那么负利润就等价于利润至少为 0 的情况。所以说这种情况就等价于 dp[i][j][0] ，可以对 k - p[i] 的结果与 0 取一个 max 。

综上，状态转移方程为：dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - g[i - 1]][max(0, k - p[i - 1])] ;

初始化： 当没有任务的时候，利润为 0 ，此时无论人数限制为多少，都能找到一个空集的方案。 因此初始化 dp[0][j][0] 的位置为 1 ，其中 0 <= j <= n 

填表顺序： 保证第一维i 从小到大即可。

返回值： 根据状态表示，返回 dp[len][n][minProfit] ，其中 len 表示字符串数组的长度。

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        // dp[i][j][k] 表示：从前i个计划中挑选，总人数不超过j，总利润至少为k，一共有多少种选法
        const int MOD = 1e9 + 7; // 注意结果取模
        int len = group.size();
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));
        for(int j = 0; j <= n; j++)
        {
            dp[0][j][0] = 1; // 初始化
        }
        for(int i = 1; i <= len; ++i)
        {
            for(int j = 0; j <= n; ++j)
            {
                for(int k = 0; k <= minProfit; ++k)
                {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if(j >= group[i - 1])
                        dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[i][j][k] %= MOD; // 注意结果取模
                }
            }
        }
        return dp[len][n][minProfit];
    }
};

代码优化

        所有的背包问题，都可以进行空间上的优化。 对于二维费用的 01 背包问题，优化还是和之前的01背包类似，删掉第一维，然后修改其他维度的遍历顺序：

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        // dp[i][j][k] 表示：从前i个计划中挑选，总人数不超过j，总利润至少为k，一共有多少种选法
        const int MOD = 1e9 + 7; // 注意结果取模
        int len = group.size();
        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));
        for(int j = 0; j <= n; j++)
        {
            dp[j][0] = 1; // 初始化
        }
        for(int i = 1; i <= len; ++i)
        {
            for(int j = n; j >= group[i - 1]; --j)
            {
                for(int k = minProfit; k >= 0; --k)
                {
                    dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[j][k] %= MOD; // 注意结果取模
                }
            }
        }
        return dp[n][minProfit];
    }
};