盈利计划

标签: 数组 动态规划

难度: Hard

集团里有 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

Submission

运行时间: 307 ms

内存: 16.6 MB

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        mod = 10 ** 9 + 7

        # 容斥原理 g <= n, p >= minProfit的组合个数为 g<=n的个数减去g<=n,p < minProft的个数
        # 先求 g<=n 的组合数
        dp1 = [0] * (n+1)
        dp1[0] = 1
        for g in group:
            for i in range(n,g-1,-1):
                dp1[i] += dp1[i-g]
        # p < minProfit的组合数为0
        if not minProfit:
            return sum(dp1) % mod
        
        # 求 g <= n, p < minProfit的组合数
        dp2 = [[0] * minProfit for _ in range(n+1)]
        dp2[0][0] = 1
        for g,p in zip(group, profit):
            for i in range(n,g-1,-1):
                for j in range(minProfit-1,p-1,-1):
                    dp2[i][j] += dp2[i-g][j-p]
        return (sum(dp1) - sum(sum(dp2[i]) for i in range(n+1))) % mod

Explain

这个题解使用了动态规划和容斥原理。首先使用动态规划求出员工数不超过n的所有组合数，然后再求出利润小于minProfit的组合数。最后根据容斥原理，用员工数不超过n的组合数减去利润小于minProfit的组合数，得到员工数不超过n且利润不小于minProfit的组合数。

时间复杂度: O(n^2+n*minProfit)

空间复杂度: O(n*minProfit)

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        mod = 10 ** 9 + 7

        # 容斥原理 g <= n, p >= minProfit的组合个数为 g<=n的个数减去g<=n,p < minProft的个数
        # 先求 g<=n 的组合数
        dp1 = [0] * (n+1)
        dp1[0] = 1
        for g in group:
            for i in range(n,g-1,-1):
                dp1[i] += dp1[i-g]
        # p < minProfit的组合数为0
        if not minProfit:
            return sum(dp1) % mod
        
        # 求 g <= n, p < minProfit的组合数
        dp2 = [[0] * minProfit for _ in range(n+1)]
        dp2[0][0] = 1
        for g,p in zip(group, profit):
            for i in range(n,g-1,-1):
                for j in range(minProfit-1,p-1,-1):
                    dp2[i][j] += dp2[i-g][j-p]
        return (sum(dp1) - sum(sum(dp2[i]) for i in range(n+1))) % mod

Explore

在动态规划中，dp1数组用于计算不同的员工组合数，其中dp1[i]代表使用i个员工可以形成的组合数。初始化dp1[0] = 1是因为使用0名员工只有一种情况，即不使用任何员工。这是组合计算的基础，用于在后续迭代中累加新的员工组合。其他位置初始化为0的原因是，这些位置代表的是初始状态下使用相应数量的员工的组合数是未知的，因此从0开始计数。

在更新dp1数组时，使用了从后向前的更新方式（即从n到g）。这种更新顺序确保在计算dp1[i]时，加入的dp1[i-g]是在没有考虑当前员工组g之前的状态，从而避免了组合的重复计算。这样的迭代顺序确保每种组合只被计算一次，防止同一组员工在同一轮更新中被重复考虑。

dp2数组负责计算在员工数不超过n且利润小于minProfit的组合数。在更新时从后向前（即从minProfit-1到p），是为了确保在更新当前利润j的组合数时，所引用的dp2[i-g][j-p]是未加入当前利润p之前的状态。这种从大到小的更新防止了当前轮次内的重复计算，确保每种利润组合都是基于前一状态的结果，避免了重复计算的错误。

容斥原理在这个问题中被用来计算最终符合条件的组合数。具体来说，首先计算所有可能的组合数（即员工数不超过n的组合数），然后计算不符合利润要求（即利润小于minProfit的组合数）。根据容斥原理，最终符合条件的组合数等于总的可能组合数减去不符合利润要求的组合数。这样可以有效地从所有可能的组合中排除那些不满足利润条件的情况，得到精确的符合要求的组合总数。