Profitable Schemes

给一个数字n,表示n个人, 给一个数字p, 表示最小的收益, 给两个数组,表示工作和工作需要的人, 问最多使用n个人并且满足最小收益的工作一共有多少种组合?

这个题一眼肯定是动态规划, 但是因为是求多少种组合, 所以每个条件都单做一维.

Let dp[i][g][p] to be the first i’th jobs (including) with exact g members used and having exact p profit.

首先要初始化这个dp, 那么dp[0][0][0]是1

从背包问题,宽泛考虑, 可以知道, 如果不选当前的i, 那么对应的g和p就不会增加, 所以这也是一种组合:

   dp[i][g][p] += dp[i - 1][g][p]

当决定了选i’th job, 就要考虑当前i是否满足限制人数(不满足则不选):

if(g + group[i - 1] > G){
   continue;//skip
}

通过上面这行后, 确定了ith job肯定能干, 接着考虑下面的, 如果ith job的profit和当前profit加起来超过了P(最小profit), 因为其实超过了多少无所谓, 我们就把所有超过P的job放到P的位置上, 这样便于统计.

if(p + profit[i - 1] > P){  
    dp[i][g + group[i - 1]][P] += dp[i - 1][g][p]; 
    dp[i][g + group[i - 1]][P] %= mod;
}

如果加起来还是没有超过p, 那么我们只能先存着, 因为当前的运算可能作为以后某个答案的子集.

else{
     dp[i][g + group[i - 1]][p + profit[i - 1]] += dp[i - 1][g][p];
     dp[i][g + group[i - 1]][p + profit[i - 1]] %= mod;
}

以上就是dp的构建, 最后的答案因为我们的dp只迭代了包含前i个job的子问题, 子问题并没有对人数进行迭代, 人数从0到G都是满足题意的答案, 所以需要在dp的中找到这些答案并且加起来.

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

全代码:

class Solution {
    public int profitableSchemes(int G, int P, int[] group, int[] profit) { 
        int mod = 1_000_000_007;
        int n = group.length;
        int[][][] dp = new int[n + 1][G + 1][P + 1];
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int g = 0; g <= G; g++) {
                for (int p = 0; p <= P; p++) {
                    dp[i][g][p] += dp[i - 1][g][p];// not selected i
                    dp[i][g][p] %= mod; 
                    if(g + group[i - 1] > G) // if need too many members
                        continue;//skip
                    if(p + profit[i - 1] > P){ // if it is already over profit
                        dp[i][g + group[i - 1]][P] += f[i - 1][g][p]; // add it to P(the target profit)
                        dp[i][g + group[i - 1]][P] %= mod;
                    }
                    else{
                        dp[i][g + group[i - 1]][p + profit[i - 1]] += dp[i - 1][g][p]; // select i as a part of the subset 
                        dp[i][g + group[i - 1]][p + profit[i - 1]] %= mod;
                    }
                }
            }
        }
        int res = 0;
        for (int i = 0; i <= G; i++) {
            res += dp[n][i][P];
            res %= mod;
        }
        return res;
    }
}