一、题目

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

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

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

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

点击查看原题

二、思路

1）动态规划

本题还是背包问题，只不过从原来的01背包进行了扩展。
设定三维数组dp[i][j][k]代表前i个工作，使用j个人，最小盈利k的计划数。
有两种情况：

  • 能完成第i个工作的情况，即j>=group[i-1]（人数保证起码能够完成工作group[i-1]），那么计划数应该为dp[i][j-group[i-1]][max(0, k-profit[i-1])]
  • 不能完成第i个工作，那么计划数就继承i-1的状态，为dp[i-1][j][k]

可以得到状态转移方程：
879. 盈利计划-每日一题 - 图1
最后遍历求和，所有工作不同人数能够达到的盈利计划数总和为所求解。

2）优化

由于上述方程的i状态，只依赖于i-1，可以减少一个维度

三、代码

1）动态规划

  1. class Solution {
  2.     public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
  3.         int[][][] dp = new int[group.length + 1][n + 1][minProfit + 1];
  4.         dp[0][0][0] = 1;    // 0个任务0个工人完成最小价值0的计划数为1
  5.         for (int i = 1; i < dp.length; i++) {
  6.             int member = group[i-1], earn = profit[i-1];
  7.             for (int j = 0; j < dp[0].length; j++) {
  8.                 for (int k = 0; k < dp[0][0].length; k++) {
  9.                     if (j < member) {    // 当无法完成第i个任务，就继承i-1的状态
  10.                         dp[i][j][k] = dp[i-1][j][k];
  11.                     } else {
  12.                         // 如果可以完成第i个任务
  13.                         // 不完成第i个任务情况+完成第i个任务，从而得到最小盈利k的所有计划数
  14.                         dp[i][j][k] = (dp[i-1][j][k] + dp[i-1][j-member][Math.max(0, k-earn)]) % 1000000007;
  15.                     }
  16.                 }
  17.             }
  18.         }
  19.         int ans = 0;
  20.         // 所有工作，不同人数，能够达到的盈利计划数总和
  21.         for (int j = 0; j < dp[0].length; j++) {
  22.             ans = (ans + dp[dp.length - 1][j][minProfit]) % 1000000007;
  23.         }
  24.         return ans;
  25.     }
  26. }

时间复杂度为O(group.lengthnminProfit)，空间复杂度为O(group.lengthnminProfit)

2）优化

  1. class Solution {
  2.     public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
  3.         int[][] dp = new int[n + 1][minProfit + 1];
  4.         for (int i = 0; i < dp.length; i++) {
  5.             dp[i][0] = 1;
  6.         }
  7.         for (int i = 0; i < group.length; i++) {
  8.             int member = group[i], earn = profit[i];
  9.             for (int j = dp.length - 1; j >= member; j--) {
  10.                 for (int k = dp[0].length - 1; k >= 0; k--) {
  11.                     dp[j][k] = (dp[j][k] + dp[j-member][Math.max(0, k-earn)]) % 1000000007;
  12.                 }
  13.             }
  14.         }
  15.         return dp[n][minProfit];
  16.     }
  17. }

时间复杂度为O(group.lengthnminProfit)，空间复杂度为O(n*minProfit)