Code Implementation

MOD = 10**9 + 7
class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        # dp[people][profit] = number of ways
        dp = [[0] * (minProfit + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for g, p in zip(group, profit):
            # Copy dp to avoid in-place overwrite
            ndp = [row[:] for row in dp]
            for people in range(n - g + 1):
                for pf in range(minProfit + 1):
                    if dp[people][pf]:
                        new_people = people + g
                        new_profit = min(minProfit, pf + p)
                        ndp[new_people][new_profit] = (ndp[new_people][new_profit] + dp[people][pf]) % MOD
            dp = ndp
        return sum(dp[people][minProfit] for people in range(n + 1)) % MOD
    

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        const int MOD = 1e9 + 7;
        int m = group.size();
        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1, 0));
        dp[0][0] = 1;
        for (int k = 0; k < m; ++k) {
            int g = group[k], p = profit[k];
            vector<vector<int>> ndp = dp;
            for (int people = 0; people + g <= n; ++people) {
                for (int pf = 0; pf <= minProfit; ++pf) {
                    if (dp[people][pf]) {
                        int new_people = people + g;
                        int new_profit = min(minProfit, pf + p);
                        ndp[new_people][new_profit] = (ndp[new_people][new_profit] + dp[people][pf]) % MOD;
                    }
                }
            }
            dp = ndp;
        }
        int res = 0;
        for (int people = 0; people <= n; ++people)
            res = (res + dp[people][minProfit]) % MOD;
        return res;
    }
};
    

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int MOD = 1_000_000_007;
        int[][] dp = new int[n + 1][minProfit + 1];
        dp[0][0] = 1;
        for (int k = 0; k < group.length; ++k) {
            int g = group[k], p = profit[k];
            int[][] ndp = new int[n + 1][minProfit + 1];
            for (int i = 0; i <= n; ++i)
                System.arraycopy(dp[i], 0, ndp[i], 0, minProfit + 1);
            for (int people = 0; people + g <= n; ++people) {
                for (int pf = 0; pf <= minProfit; ++pf) {
                    if (dp[people][pf] > 0) {
                        int new_people = people + g;
                        int new_profit = Math.min(minProfit, pf + p);
                        ndp[new_people][new_profit] = (ndp[new_people][new_profit] + dp[people][pf]) % MOD;
                    }
                }
            }
            dp = ndp;
        }
        int res = 0;
        for (int people = 0; people <= n; ++people)
            res = (res + dp[people][minProfit]) % MOD;
        return res;
    }
}
    

var profitableSchemes = function(n, minProfit, group, profit) {
    const MOD = 1e9 + 7;
    let dp = Array.from({length: n + 1}, () => Array(minProfit + 1).fill(0));
    dp[0][0] = 1;
    for (let k = 0; k < group.length; ++k) {
        let g = group[k], p = profit[k];
        let ndp = dp.map(row => row.slice());
        for (let people = 0; people + g <= n; ++people) {
            for (let pf = 0; pf <= minProfit; ++pf) {
                if (dp[people][pf]) {
                    let new_people = people + g;
                    let new_profit = Math.min(minProfit, pf + p);
                    ndp[new_people][new_profit] = (ndp[new_people][new_profit] + dp[people][pf]) % MOD;
                }
            }
        }
        dp = ndp;
    }
    let res = 0;
    for (let people = 0; people <= n; ++people)
        res = (res + dp[people][minProfit]) % MOD;
    return res;
};
    

Problem Description

You are given an integer n representing the total number of members in a gang, an integer minProfit representing the minimum profit required, and two integer arrays group and profit of equal length. Each group[i] is the number of members required to execute the i-th crime, and profit[i] is the profit from that crime.

The goal is to determine how many different schemes can be chosen such that:

• The total number of gang members used does not exceed n.
• The total profit is at least minProfit.

Thought Process

This problem is a variation of the classic knapsack problem, but with two constraints: the number of people (like weight) and the minimum profit (like value). The challenge is to count the number of valid schemes, not just find one optimal solution.

The brute-force way would be to try every subset of crimes, calculate the total number of people and profit, and count those that meet the requirements. However, with up to 100 crimes, this is computationally infeasible because the number of subsets grows exponentially.

To optimize, we can use dynamic programming (DP) to efficiently count the number of ways to reach every possible combination of people used and profit achieved. This is similar to how we solve multi-dimensional knapsack problems, where each DP state represents a unique combination of used resources and accumulated value.

Solution Approach

• State Definition:
  Define a DP table dp[people][profit] where dp[i][j] is the number of ways to choose a subset of crimes using exactly i members and achieving at least j profit.
• Initialization:
  There is exactly one way to achieve 0 profit with 0 people: choose nothing. So dp[0][0] = 1.
• Transition:
  For each crime, consider two options:
  • Don't take the crime: the DP state remains the same.
  • Take the crime: add its group size and profit to the current state, but only if the total people used does not exceed n.
  When updating profit, cap it at minProfit because any profit above this is equivalent for our purpose.
• Order of Processing:
  To avoid overcounting, process the DP table for each crime in a way that ensures each combination is only counted once. It's common to use a copy of the DP table or iterate in reverse.
• Result Calculation:
  The answer is the sum over all dp[people][minProfit] for every possible number of people used (from 0 to n), since profit at least minProfit is required.

Example Walkthrough

Suppose n = 5, minProfit = 3, group = [2, 2], profit = [2, 3].

• Start: dp[0][0] = 1 (one way to do nothing).
• First crime (group=2, profit=2):
  • Add this crime to dp[0][0]: now dp[2][2] += 1 (using 2 people, profit 2).
• Second crime (group=2, profit=3):
  • Add this crime to dp[0][0]: dp[2][3] += 1 (using 2 people, profit 3).
  • Add this crime to dp[2][2]: dp[4][min(2+3,3)] += 1 → dp[4][3] += 1 (using 4 people, profit at least 3).
• Final count:
  • Sum up dp[people][3] for people in 0..5: dp[2][3] + dp[4][3] = 1 + 1 = 2.
• So, there are 2 schemes: pick only the second crime, or pick both crimes.

Time and Space Complexity

• Brute-force approach:
  Time complexity is O(2^m) where m is the number of crimes, as every subset is checked.
• Optimized DP approach:
  Time complexity is O(m * n * minProfit) because for each crime, we process all (n+1)*(minProfit+1) states.
• Space complexity:
  O(n * minProfit) for the DP table.
• This is efficient for the constraints (n and minProfit up to 100, m up to 100).

Summary

The Profitable Schemes problem is a two-dimensional knapsack variant where we count the number of crime subsets meeting both people and profit constraints. By using dynamic programming to track the number of ways to achieve each possible state, we avoid exponential brute-force and arrive at an efficient, elegant solution. The key insight is to treat profit and people as state variables and carefully update the DP table for each crime, ensuring we count every valid scheme exactly once.