LeetCode 879 - Profitable Schemes

https://leetcode.com/problems/profitable-schemes/

There are G people in a gang, and a list of various crimes they could commit.

The i-th crime generates a profit[i] and requires group[i] gang members to participate.

If a gang member participates in one crime, that member can't participate in another crime.

Let's call a profitable scheme any subset of these crimes that generates at least P profit, and the total number of gang members participating in that subset of crimes is at most G.

How many schemes can be chosen?  Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: G = 5, P = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation: 
To make a profit of at least 3, the gang could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.

Example 2:

Input: G = 10, P = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation: 
To make a profit of at least 5, the gang could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2). 

Note:

1. 1 <= G <= 100
2. 0 <= P <= 100
3. 1 <= group[i] <= 100
4. 0 <= profit[i] <= 100
5. 1 <= group.length = profit.length <= 100

https://leetcode.com/articles/profitable-schemes/

• Time Complexity: $O(N * P * G)$, where $N$ is the number of crimes available to the gang.
• Space Complexity: $O(P * G)$. 

We don't care about the profit of the scheme if it is $\geq P$, because it surely will be over the threshold of profitability required. Similarly, we don't care about the number of people required in the scheme if it is $> G$, since we know the scheme will be too big for the gang to execute.

As a result, the bounds are small enough to use dynamic programming. Let's keep track of cur[p][g], the number of schemes with profitability $p$ and requiring $g$ gang members: except we'll say (without changing the answer) that all schemes that profit at least P dollars will instead profit exactly P dollars.

Algorithm

Keeping track of cur[p][g] as defined above, let's understand how it changes as we consider 1 extra crime that will profit p0 and require g0 gang members. We will put the updated counts into cur2.

For each possible scheme with profit p1 and group size g1, that scheme plus the extra crime (p0, g0) being considered, has a profit of p2 = min(p1 + p0, P), and uses a group size of g2 = g1 + g0.

public int profitableSchemes(int G, int P, int[] group, int[] profit) {
    int MOD = 1_000_000_007;
    int N = group.length;
    long[][][] dp = new long[2][P+1][G+1];
    dp[0][0][0] = 1;

    for (int i = 0; i < N; ++i) {
        int p0 = profit[i];  // the current crime profit
        int g0 = group[i];  // the current crime group size

        long[][] cur = dp[i % 2];
        long[][] cur2 = dp[(i + 1) % 2];

        // Deep copy cur into cur2
        for (int jp = 0; jp <= P; ++jp)
            for (int jg = 0; jg <= G; ++jg)
                cur2[jp][jg] = cur[jp][jg];

        for (int p1 = 0; p1 <= P; ++p1) {  // p1 : the current profit
            // p2 : the new profit after committing this crime
            int p2 = Math.min(p1 + p0, P);
            for (int g1 = 0; g1 <= G - g0; ++g1) {  // g1 : the current group size
                // g2 : the new group size after committing this crime
                int g2 = g1 + g0;
                cur2[p2][g2] += cur[p1][g1];
                cur2[p2][g2] %= MOD;
            }
        }
    }

    // Sum all schemes with profit P and group size 0 <= g <= G.
    long ans = 0;
    for (long x: dp[N%2][P])
        ans += x;

    return (int) ans;
}

https://leetcode.com/problems/profitable-schemes/discuss/157099/Java-original-3d-to-2d-DP-solution

dp[k][i][j] means for first k crime with i members and at least j profit, what is total schemes can be chosen.
And we need this Math.max(0, j - p), because this is for at least j profit.

dp[k][i][j] = dp[k - 1][i][j] + dp[k - 1][i - current group][Math.max(0, j - current profit)]

This is 3d original solution:

class Solution {
    private int mod = (int)1e9 + 7;
    public int profitableSchemes(int G, int P, int[] group, int[] profit) {
        int[][][] dp = new int[group.length + 1][G + 1][P + 1];
        dp[0][0][0] = 1;
        for (int k = 1; k <= group.length; k++) {
            int g = group[k - 1];
            int p = profit[k - 1];
            for (int i = 0; i <= G; i++) {
                for (int j = 0; j <= P; j++) {
                    dp[k][i][j] = dp[k - 1][i][j];
                    if (i >= g) {
                        dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i - g][Math.max(0, j - p)])%mod;
                    }
                }
            }
        }
        int sum = 0;                                                       
        for(int i = 0; i <= G; i++){
            sum = (sum + dp[group.length][i][P])%mod;
        }
        return sum;
    }
}

Because all k dimension only depends on k - 1 dimension, so we can improve it to 2D array which only has i and j dimension.
Just be careful about that i and j should be decrease, in order to get correct old k - 1 dimension value.

class Solution {
    private int mod = (int)1e9 + 7;
    public int profitableSchemes(int G, int P, int[] group, int[] profit) {
        int[][] dp = new int[G + 1][P + 1];
        dp[0][0] = 1;
        for (int k = 1; k <= group.length; k++) {
            int g = group[k - 1];
            int p = profit[k - 1];
            for (int i = G; i >= g; i--) {
                for (int j = P; j >= 0; j--) {
                    dp[i][j] = (dp[i][j] + dp[i - g][Math.max(0, j - p)])%mod;
                }
            }
        }
        int sum = 0;                                                       
        for(int i = 0; i <= G; i++){
            sum = (sum + dp[i][P])%mod;
        }
        return sum;
    }
}

https://leetcode.com/problems/profitable-schemes/discuss/154617/C%2B%2BJavaPython-DP

Well, it is a Knapsack problem and my first intuition is dp.

dp[i][j] means the count of schemes with i profit and j members.

The dp equation is simple here:
dp[i + p][j + g] += dp[i][j]) if i + p < P
dp[P][j + g] += dp[i][j]) if i + p >= P

Don't forget to take care of overflow.

For each pair (p, g) of (profit, group), I update the count in dp.

Time Complexity:
O(NPG)

    public int profitableSchemes(int G, int P, int[] group, int[] profit) {
        int[][] dp = new int[P + 1][G + 1];
        dp[0][0] = 1;
        int res = 0, mod = (int)1e9 + 7;
        for (int k = 0; k < group.length; k++) {
            int g = group[k], p = profit[k];
            for (int i = P; i >= 0; i--)
                for (int j = G - g; j >= 0; j--)
                    dp[Math.min(i + p, P)][j + g] = (dp[Math.min(i + p, P)][j + g] + dp[i][j]) % mod;
        }
        for (int x : dp[P]) res = (res + x) % mod;
        return res;
    }

We don't care about the profit of the scheme if it is $\geq P$, because it surely will be over the threshold of profitability required. Similarly, we don't care about the number of people required in the scheme if it is $> G$, since we know the scheme will be too big for the gang to execute.

As a result, the bounds are small enough to use dynamic programming. Let's keep track of cur[p][g], the number of schemes with profitability $p$ and requiring $g$ gang members: except we'll say (without changing the answer) that all schemes that profit at least P dollars will instead profit exactly P dollars.

Algorithm

Keeping track of cur[p][g] as defined above, let's understand how it changes as we consider 1 extra crime that will profit p0 and require g0 gang members. We will put the updated counts into cur2.

For each possible scheme with profit p1 and group size g1, that scheme plus the extra crime (p0, g0) being considered, has a profit of p2 = min(p1 + p0, P), and uses a group size of g2 = g1 + g0.

  public int profitableSchemes(int G, int P, int[] group, int[] profit) {

    int MOD = 1_000_000_007;

    int N = group.length;

    long[][][] dp = new long[2][P + 1][G + 1];

    dp[0][0][0] = 1;

    for (int i = 0; i < N; ++i) {

      int p0 = profit[i]; // the current crime profit

      int g0 = group[i]; // the current crime group size

      long[][] cur = dp[i % 2];

      long[][] cur2 = dp[(i + 1) % 2];

      // Deep copy cur into cur2

      for (int jp = 0; jp <= P; ++jp)

        for (int jg = 0; jg <= G; ++jg)

          cur2[jp][jg] = cur[jp][jg];

      for (int p1 = 0; p1 <= P; ++p1) { // p1 : the current profit

        // p2 : the new profit after committing this crime

        int p2 = Math.min(p1 + p0, P);

        for (int g1 = 0; g1 <= G - g0; ++g1) { // g1 : the current group size

          // g2 : the new group size after committing this crime

          int g2 = g1 + g0;

          cur2[p2][g2] += cur[p1][g1];

          cur2[p2][g2] %= MOD;

        }

      }

    }

    // Sum all schemes with profit P and group size 0 <= g <= G.

    long ans = 0;

    for (long x : dp[N % 2][P])

      ans += x;

    return (int) ans;

  }

https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-879-profitable-schemes/

v1: Dimension reduction by copying.

int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {    
  const int kMod = 1000000007;
  const int K = group.size();
  // dp[i][j]:= # of schemes of making profit i with j people.
  vector<vector<int>> dp(P + 1, vector<int>(G + 1, 0));
  dp[0][0] = 1;

  for (int k = 1; k <= K; ++k) {
    auto tmp = dp;
    const int p = profit[k - 1];
    const int g = group[k - 1];
    for (int i = 0; i <= P; ++i)    
      for (int j = 0; j <= G; ++j)
        tmp[i][j] = (tmp[i][j] + (j < g ? 0 : dp[max(0, i - p)][j - g])) % kMod;
    dp.swap(tmp);
  }
  return accumulate(begin(dp[P]), end(dp[P]), 0LL) % kMod;
}

v2: Dimension reduction by using rolling array.

int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
  const int kMod = 1000000007;
  // dp[i][j]:= # of schemes of making profit i with j people.
  vector<vector<int>> dp(P + 1, vector<int>(G + 1, 0));
  dp[0][0] = 1;
  const int K = group.size();
  for (int k = 0; k < K; ++k) {
    const int p = profit[k];
    const int g = group[k];
    for (int i = P; i >= 0; --i) {
      const int ip = min(P, i + p);
      for (int j = G - g; j >= 0; --j)
        dp[ip][j + g] = (dp[ip][j + g] + dp[i][j]) % kMod;
    }
  }
  return accumulate(begin(dp[P]), end(dp[P]), 0LL) % kMod;
}

https://www.acwing.com/solution/LeetCode/content/581/

帮派里有 G 名成员，他们可能犯下各种各样的罪行。

第 i 种犯罪会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。

让我们把这些犯罪的任何子集称为盈利计划，该计划至少产生 P 的利润。

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

样例

输入：G = 5, P = 3, group = [2,2], profit = [2,3]
输出：2
解释： 
至少产生 3 的利润，该帮派可以犯下罪 0 和罪 1，或仅犯下罪 1。
总的来说，有两种方案。

输入：G = 10, P = 5, group = [2,3,5], profit = [6,7,8]
输出：7
解释：
至少产生 5 的利润，只要他们犯其中一种罪就行，所以该帮派可以犯下任何罪行。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2)。




1. 题目要求是统计利润至少为 P，且人数最多为 G 的方案数。由于利润最多有可能达到 100 * n，数据范围过大而不方便进行动态规划，可以考虑该问题的对偶问题。即统计人数最多为 G 的方案数，减去利润小于 P，且统计人数最多为 G 的方案数。
2. 对于第一部分，动态规划的状态为 $s(i,j)$，表示考虑了前 i 个计划，参与人数为 j 的方案数是多少。对于第 i 个计划，$s(i,j)=s(i,j)+s(i-1,j-group[i])$。初始值 $s(0,0)=1$。人数最多为 G 的方案数为 $\sum _{j=0}^{G}s(n,j)$。实际上可以省略掉第一维。
3. 对于第二部分，动态规划的状态为 $f(i,j,k)$，表示考虑了前 i 个计划，参与人数为 j 的方案数，且利润为 k 的方案数是多少。对于第 i 个计划，$f(i,j,k)=f(i,j,k)+f(i-1,j-group[i],k-profit[i])$。初始值 $f(0,0,0)=1$。利润小于 P，且统计人数最多为 G 的方案数为 $\sum _{j=k=0}^{j<=G,k<P}f(n,j,k)$。实际上可以仍然省略掉第一维。
4. 最终答案就是两部分做差。

X. Video
花花酱 LeetCode 879. Profitable Schemes - 刷题找工作 EP212