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就不会增加, 所以这也是一种组合:
|
1 |
dp[i][g][p] += dp[i - 1][g][p] |
当决定了选i’th job, 就要考虑当前i是否满足限制人数(不满足则不选):
|
1 2 3 |
if(g + group[i - 1] > G){ continue;//skip } |
通过上面这行后, 确定了ith job肯定能干, 接着考虑下面的, 如果ith job的profit和当前profit加起来超过了P(最小profit), 因为其实超过了多少无所谓, 我们就把所有超过P的job放到P的位置上, 这样便于统计.
|
1 2 3 4 5 |
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, 那么我们只能先存着, 因为当前的运算可能作为以后某个答案的子集.
|
1 2 3 4 |
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的中找到这些答案并且加起来.
|
1 2 3 4 5 |
int res = 0; for (int i = 0; i <= G; i++) { res += dp[n][i][P]; res %= mod; } |
全代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
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; } } |