|
| 1 | +/** |
| 2 | + * There are G people in a gang, and a list of various crimes they could commit. |
| 3 | + * |
| 4 | + * The i-th crime generates a profit[i] and requires group[i] gang members to |
| 5 | + * participate. |
| 6 | + * |
| 7 | + * If a gang member participates in one crime, that member can't participate in |
| 8 | + * another crime. |
| 9 | + * |
| 10 | + * Let's call a profitable scheme any subset of these crimes that generates at |
| 11 | + * least P profit, and the total number of gang members participating in that |
| 12 | + * subset of crimes is at most G. |
| 13 | + * |
| 14 | + * How many schemes can be chosen? Since the answer may be very large, return |
| 15 | + * ∂it modulo 10^9 + 7. |
| 16 | + * |
| 17 | + * Example 1: |
| 18 | + * Input: G = 5, P = 3, group = [2,2], profit = [2,3] |
| 19 | + * Output: 2 |
| 20 | + * Explanation: |
| 21 | + * To make a profit of at least 3, the gang could either commit crimes 0 and 1, |
| 22 | + * or just crime 1. |
| 23 | + * In total, there are 2 schemes. |
| 24 | + * |
| 25 | + * Example 2: |
| 26 | + * Input: G = 10, P = 5, group = [2,3,5], profit = [6,7,8] |
| 27 | + * Output: 7 |
| 28 | + * Explanation: |
| 29 | + * To make a profit of at least 5, the gang could commit any crimes, as long |
| 30 | + * as they commit one. |
| 31 | + * |
| 32 | + * There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2). |
| 33 | + * |
| 34 | + * Note: |
| 35 | + * 1 <= G <= 100 |
| 36 | + * 0 <= P <= 100 |
| 37 | + * 1 <= group[i] <= 100 |
| 38 | + * 0 <= profit[i] <= 100 |
| 39 | + * 1 <= group.length = profit.length <= 100 |
| 40 | + */ |
| 41 | + |
| 42 | +publicclassProfitableSchemes879 { |
| 43 | + |
| 44 | +publicintprofitableSchemes(intG,intP,int[]group,int[]profit) { |
| 45 | +intK =group.length; |
| 46 | +int[][][]dp =newint[K +1][P +1][G +1]; |
| 47 | +dp[0][0][0] =1; |
| 48 | +intmod = (int)1e9 +7; |
| 49 | +for (intk=1;k<=K;k++) { |
| 50 | +intpk =profit[k-1]; |
| 51 | +intgk =group[k-1]; |
| 52 | +for (inti=0;i<=P;i++) { |
| 53 | +for (intj=0;j<=G;j++) { |
| 54 | +dp[k][i][j] = (dp[k-1][i][j] + (j <gk ?0 :dp[k-1][Math.max(0,i-pk)][j -gk])) %mod; |
| 55 | + } |
| 56 | + } |
| 57 | + } |
| 58 | + |
| 59 | +intres =0; |
| 60 | +for (inta:dp[K][P]) { |
| 61 | +res = (res +a) %mod; |
| 62 | + } |
| 63 | +returnres; |
| 64 | + } |
| 65 | + |
| 66 | + |
| 67 | +publicintprofitableSchemes2(intG,intP,int[]group,int[]profit) { |
| 68 | +intK =group.length; |
| 69 | +int[][]dp =newint[P +1][G +1]; |
| 70 | +dp[0][0] =1; |
| 71 | +intmod = (int)1e9 +7; |
| 72 | +for (intk=1;k<=K;k++) { |
| 73 | +intpk =profit[k-1]; |
| 74 | +intgk =group[k-1]; |
| 75 | + |
| 76 | +int[][]tmp =newint[P +1][G +1]; |
| 77 | +for (inti=0;i<=P;i++) { |
| 78 | +for (intj=0;j<=G;j++) { |
| 79 | +tmp[i][j] =dp[i][j]; |
| 80 | + } |
| 81 | + } |
| 82 | + |
| 83 | +for (inti=0;i<=P;i++) { |
| 84 | +for (intj=0;j<=G;j++) { |
| 85 | +dp[i][j] = (tmp[i][j] + (j <gk ?0 :tmp[Math.max(0,i-pk)][j -gk])) %mod; |
| 86 | + } |
| 87 | + } |
| 88 | + } |
| 89 | + |
| 90 | +intres =0; |
| 91 | +for (inta:dp[P]) { |
| 92 | +res = (res +a) %mod; |
| 93 | + } |
| 94 | +returnres; |
| 95 | + } |
| 96 | + |
| 97 | + |
| 98 | +/** |
| 99 | + * https://leetcode.com/problems/profitable-schemes/solution/ |
| 100 | + */ |
| 101 | +publicintprofitableSchemes3(intG,intP,int[]group,int[]profit) { |
| 102 | +intMOD =1_000_000_007; |
| 103 | +intN =group.length; |
| 104 | +long[][][]dp =newlong[2][P+1][G+1]; |
| 105 | +dp[0][0][0] =1; |
| 106 | + |
| 107 | +for (inti =0;i <N; ++i) { |
| 108 | +intp0 =profit[i];// the current crime profit |
| 109 | +intg0 =group[i];// the current crime group size |
| 110 | + |
| 111 | +long[][]cur =dp[i %2]; |
| 112 | +long[][]cur2 =dp[(i +1) %2]; |
| 113 | + |
| 114 | +// Deep copy cur into cur2 |
| 115 | +for (intjp =0;jp <=P; ++jp) |
| 116 | +for (intjg =0;jg <=G; ++jg) |
| 117 | +cur2[jp][jg] =cur[jp][jg]; |
| 118 | + |
| 119 | +for (intp1 =0;p1 <=P; ++p1) {// p1 : the current profit |
| 120 | +// p2 : the new profit after committing this crime |
| 121 | +intp2 =Math.min(p1 +p0,P); |
| 122 | +for (intg1 =0;g1 <=G -g0; ++g1) {// g1 : the current group size |
| 123 | +// g2 : the new group size after committing this crime |
| 124 | +intg2 =g1 +g0; |
| 125 | +cur2[p2][g2] +=cur[p1][g1]; |
| 126 | +cur2[p2][g2] %=MOD; |
| 127 | + } |
| 128 | + } |
| 129 | + } |
| 130 | + |
| 131 | +// Sum all schemes with profit P and group size 0 <= g <= G. |
| 132 | +longans =0; |
| 133 | +for (longx:dp[N%2][P]) |
| 134 | +ans +=x; |
| 135 | + |
| 136 | +return (int) (ans %MOD); |
| 137 | + } |
| 138 | + |
| 139 | + |
| 140 | +/** |
| 141 | + * https://leetcode.com/problems/profitable-schemes/discuss/154617/C++JavaPython-DP |
| 142 | + */ |
| 143 | +publicintprofitableSchemes4(intG,intP,int[]group,int[]profit) { |
| 144 | +int[][]dp =newint[P +1][G +1]; |
| 145 | +dp[0][0] =1; |
| 146 | +intres =0,mod = (int)1e9 +7; |
| 147 | +for (intk =0;k <group.length;k++) { |
| 148 | +intg =group[k],p =profit[k]; |
| 149 | +for (inti =P;i >=0;i--) |
| 150 | +for (intj =G -g;j >=0;j--) |
| 151 | +dp[Math.min(i +p,P)][j +g] = (dp[Math.min(i +p,P)][j +g] +dp[i][j]) %mod; |
| 152 | + } |
| 153 | +for (intx :dp[P])res = (res +x) %mod; |
| 154 | +returnres; |
| 155 | + } |
| 156 | + |
| 157 | + |
| 158 | +/** |
| 159 | + * https://www.youtube.com/watch?v=MjOIR61txFc |
| 160 | + */ |
| 161 | +publicintprofitableSchemes5(intG,intP,int[]group,int[]profit) { |
| 162 | +intK =group.length; |
| 163 | +int[][]dp =newint[P +1][G +1]; |
| 164 | +dp[0][0] =1; |
| 165 | +intmod = (int)1e9 +7; |
| 166 | +for (intk=1;k<=K;k++) { |
| 167 | +intpk =profit[k-1]; |
| 168 | +intgk =group[k-1]; |
| 169 | +for (inti=P;i>=0;i--) { |
| 170 | +intip =Math.min(P,i +pk); |
| 171 | +for (intj=G-gk;j>=0;j--) { |
| 172 | +dp[ip][j+gk] = (dp[ip][j+gk] +dp[i][j]) %mod; |
| 173 | + } |
| 174 | + } |
| 175 | + } |
| 176 | + |
| 177 | +intres =0; |
| 178 | +for (inta:dp[P]) { |
| 179 | +res = (res +a) %mod; |
| 180 | + } |
| 181 | +returnres; |
| 182 | + } |
| 183 | + |
| 184 | + |
| 185 | +} |