Skip to content

879. Profitable Schemes

  • https://leetcode.com/problems/profitable-schemes/description/
  • 给人数，任务需要的人数，最小利益，求满足最小利益的方案数

思路

  • 动态规划，有三个限制条件，用这三个建立一个三位数组作为 dp
  • 本题解法的三个维度分别为：当前可选择的工作 i，已选择的小组员工人数 j，以及目前状态的工作获利下限 k。
  • 状态转移方程
  • 不能开展工作：dp[i][j][k]=dp[i−1][j][k]
  • 能开展：dp[i][j][k]=dp[i−1][j][k]+dp[i−1]j−group[i]][max(0,k−profit[i])]

代码

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = profit.length;
        int[][][] dp = new int[len + 1][n + 1][minProfit + 1];
        int mod = (int)1e9+7;
        dp[0][0][0] = 1;
        for(int i = 1; i <= len; i++){
            int need = group[i - 1];
            int get = profit[i - 1];
            for(int j = 0; j <= n; j++){
                for(int k = 0; k <= minProfit; k++){
                    if(j < need){
                        // no enough people, can't do the work
                        // thus, the dp = last task's dp
                        dp[i][j][k] = dp[i - 1][j][k];
                    }else{
                        dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - need][Math.max(0, k-get)]) % mod;
                    }
                }
            }
        }
        // for(int i = 0; i < len; i++){
        //     for(int j = 0; j < n; j++){
        //         System.out.print(Arrays.toString(dp[i][j]));
        //     }
        //     System.out.print("\n");
        // }


        int res = 0;
        for(int i = 0; i <= n; i++){
            res = (res + dp[len][i][minProfit]) % mod;
        }

        return res;
    }
}

递归方案

  • 对于每个任务，有做或者不做两种可能，这样就是一个二叉树。
class Solution {
    int mod = 1000000007;
    int[][][] memo = new int[101][101][101];

    int find(int pos, int count, int profit, int n, int minProfit, int[] group, int[] profits) {
        if (pos == group.length) {
            // If profit exceeds the minimum required; it's a profitable scheme.
            return profit >= minProfit ? 1 : 0;
        }

        if (memo[pos][count][profit] != -1) {
            // Repeated subproblem, return the stored answer.
            return memo[pos][count][profit];
        }

        // Ways to get a profitable scheme without this crime.
        int totalWays = find(pos + 1, count, profit, n, minProfit, group, profits);
        if (count + group[pos] <= n) {
            // Adding ways to get profitable schemes, including this crime.
            totalWays += find(pos + 1, count + group[pos], Math.min(minProfit, profit + profits[pos]), n, minProfit, group, profits);
        }

        return memo[pos][count][profit] = totalWays % mod;
    }

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        // Initializing all states as -1.
        for (int i = 0; i <= group.length; i++) {
            for(int j = 0; j <= n; j++) {
                Arrays.fill(memo[i][j], -1);
            }
        }

        return find(0, 0, 0, n, minProfit, group, profit);
    }
}

参考

- https://leetcode.cn/problems/profitable-schemes/solutions/819654/ying-li-ji-hua-by-leetcode-solution-3t8o/

public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
    // len 工作的数量
    int len = group.length, MOD = (int)1e9 + 7;
    // dp[i][j][k]：前 i 个工作中选择了 j 个员工，并且满足工作利润至少为 k 的情况下盈利计划的总数目
    int[][][] dp = new int[len + 1][n + 1][minProfit + 1];
    // 初始化，员工为 0，选择了 0 个员工，工作利润为 0
    // 即什么都不做，方案数为 1
    dp[0][0][0] = 1;
    for (int i = 1; i <= len; i++) {
        // 第 i 份工作需要使用的人数
        int members = group[i - 1];
        // 第 i 份工作能获取的利润
        int earn = profit[i - 1];
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= minProfit; k++) {
                if (j < members) {
                    // 当前能提供的人工数量小于工作需要的人数，无法做该工作
                    dp[i][j][k] = dp[i - 1][j][k];
                } else {
                    // 当人能提供的人工数量满足工作需要的人数，可以做该工作
                    // 为什么是 Math.max(0, k - profit[i - 1])，k 表示当前需要的最小利润
                    // if (k >= profit[i - 1])，前 i-1 种工作中选择的利润至少要达到 k-profit[i-1]
                    // if (k < profit[i -1])，说明前 i - 1 中工作的利润只要 >= 0 即可
                    dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - members][Math.max(0, k - earn)]) % MOD;
                }
            }
        }
    }
    int sum = 0;
    for (int j = 0; j <= n; j++) {
        sum = (sum + dp[len][j][minProfit]) % MOD;
    }
    return sum;
}