Profitable Schemes Problem

Problem

There is a group of n members, and a list of various crimes they could commit. The ith crime generates a profit[i] and requires group[i] members to participate in it. If a 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 minProfit profit, and the total number of members participating in that subset of crimes is at most n.

Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo 10^9 + 7.

Examples

Example 1:

1
2
3
4
5
6

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

Example 2:

1
2
3
4
5
6

Input:
n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output:
 7
Explanation: To make a profit of at least 5, the group 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).

Solution

Method 1 – Dynamic Programming (Knapsack)

Intuition

Use dynamic programming to count the number of ways to select crimes such that the total number of members does not exceed n and the total profit is at least minProfit.

Approach

  1. Use a DP table dp[i][j][k] where i is the number of crimes considered, j is the number of members used, and k is the profit achieved (capped at minProfit).
  2. For each crime, update the DP table by considering both including and excluding the crime.
  3. The answer is the sum of all dp[len][j][minProfit] for j in 0..n.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int MOD = 1e9+7, len = group.size();
        vector<vector<vector<int>>> dp(len+1, vector<vector<int>>(n+1, vector<int>(minProfit+1)));
        dp[0][0][0] = 1;
        for (int i = 1; i <= len; ++i) {
            int g = group[i-1], p = profit[i-1];
            for (int j = 0; j <= n; ++j) {
                for (int k = 0; k <= minProfit; ++k) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if (j >= g) {
                        int newProfit = min(minProfit, k + p);
                        dp[i][j][newProfit] = (dp[i][j][newProfit] + dp[i-1][j-g][k]) % MOD;
                    }
                }
            }
        }
        int res = 0;
        for (int j = 0; j <= n; ++j) res = (res + dp[len][j][minProfit]) % MOD;
        return res;
    }
};
 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

func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
    mod := int(1e9+7)
    len := len(group)
    dp := make([][][]int, len+1)
    for i := range dp {
        dp[i] = make([][]int, n+1)
        for j := range dp[i] {
            dp[i][j] = make([]int, minProfit+1)
        }
    }
    dp[0][0][0] = 1
    for i := 1; i <= len; i++ {
        g, p := group[i-1], profit[i-1]
        for j := 0; j <= n; j++ {
            for k := 0; k <= minProfit; k++ {
                dp[i][j][k] = dp[i-1][j][k]
                if j >= g {
                    newProfit := k + p
                    if newProfit > minProfit { newProfit = minProfit }
                    dp[i][j][newProfit] = (dp[i][j][newProfit] + dp[i-1][j-g][k]) % mod
                }
            }
        }
    }
    res := 0
    for j := 0; j <= n; j++ { res = (res + dp[len][j][minProfit]) % mod }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int MOD = 1_000_000_007, len = group.length;
        int[][][] dp = new int[len+1][n+1][minProfit+1];
        dp[0][0][0] = 1;
        for (int i = 1; i <= len; ++i) {
            int g = group[i-1], p = profit[i-1];
            for (int j = 0; j <= n; ++j) {
                for (int k = 0; k <= minProfit; ++k) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if (j >= g) {
                        int newProfit = Math.min(minProfit, k + p);
                        dp[i][j][newProfit] = (dp[i][j][newProfit] + dp[i-1][j-g][k]) % MOD;
                    }
                }
            }
        }
        int res = 0;
        for (int j = 0; j <= n; ++j) res = (res + dp[len][j][minProfit]) % MOD;
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun profitableSchemes(n: Int, minProfit: Int, group: IntArray, profit: IntArray): Int {
        val MOD = 1_000_000_007
        val len = group.size
        val dp = Array(len+1) { Array(n+1) { IntArray(minProfit+1) } }
        dp[0][0][0] = 1
        for (i in 1..len) {
            val g = group[i-1]; val p = profit[i-1]
            for (j in 0..n) {
                for (k in 0..minProfit) {
                    dp[i][j][k] = dp[i-1][j][k]
                    if (j >= g) {
                        val newProfit = minOf(minProfit, k + p)
                        dp[i][j][newProfit] = (dp[i][j][newProfit] + dp[i-1][j-g][k]) % MOD
                    }
                }
            }
        }
        var res = 0
        for (j in 0..n) res = (res + dp[len][j][minProfit]) % MOD
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: list[int], profit: list[int]) -> int:
        MOD = 10**9+7
        len_ = len(group)
        dp = [[[0]*(minProfit+1) for _ in range(n+1)] for _ in range(len_+1)]
        dp[0][0][0] = 1
        for i in range(1, len_+1):
            g, p = group[i-1], profit[i-1]
            for j in range(n+1):
                for k in range(minProfit+1):
                    dp[i][j][k] = dp[i-1][j][k]
                    if j >= g:
                        newProfit = min(minProfit, k + p)
                        dp[i][j][newProfit] = (dp[i][j][newProfit] + dp[i-1][j-g][k]) % MOD
        return sum(dp[len_][j][minProfit] for j in range(n+1)) % 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

impl Solution {
    pub fn profitable_schemes(n: i32, min_profit: i32, group: Vec<i32>, profit: Vec<i32>) -> i32 {
        let n = n as usize;
        let min_profit = min_profit as usize;
        let len = group.len();
        let mut dp = vec![vec![vec![0; min_profit+1]; n+1]; len+1];
        dp[0][0][0] = 1;
        for i in 1..=len {
            let g = group[i-1] as usize;
            let p = profit[i-1] as usize;
            for j in 0..=n {
                for k in 0..=min_profit {
                    dp[i][j][k] = dp[i-1][j][k];
                    if j >= g {
                        let new_profit = std::cmp::min(min_profit, k + p);
                        dp[i][j][new_profit] = (dp[i][j][new_profit] + dp[i-1][j-g][k]) % 1_000_000_007;
                    }
                }
            }
        }
        let mut res = 0;
        for j in 0..=n { res = (res + dp[len][j][min_profit]) % 1_000_000_007; }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    profitableSchemes(n: number, minProfit: number, group: number[], profit: number[]): number {
        const MOD = 1e9+7, len = group.length;
        const dp: number[][][] = Array.from({length: len+1}, () => Array.from({length: n+1}, () => Array(minProfit+1).fill(0)));
        dp[0][0][0] = 1;
        for (let i = 1; i <= len; ++i) {
            const g = group[i-1], p = profit[i-1];
            for (let j = 0; j <= n; ++j) {
                for (let k = 0; k <= minProfit; ++k) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if (j >= g) {
                        const newProfit = Math.min(minProfit, k + p);
                        dp[i][j][newProfit] = (dp[i][j][newProfit] + dp[i-1][j-g][k]) % MOD;
                    }
                }
            }
        }
        let res = 0;
        for (let j = 0; j <= n; ++j) res = (res + dp[len][j][minProfit]) % MOD;
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(len * n * minProfit)
    • For each crime, we update a DP table of size n x minProfit, resulting in O(len * n * minProfit) operations.
  • 🧺 Space complexity: O(len * n * minProfit)
    • The DP table stores the number of ways for each combination of crimes, members, and profit.