We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Profitable Schemes

Difficulty: Hard

Problem Description

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.

Key Insights

  • We can use dynamic programming to keep track of the number of ways to achieve a certain profit with a given number of members.
  • Each crime can either be included or excluded from a scheme, leading to a combinatorial problem.
  • The DP state can be defined as 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.

Space and Time Complexity

Time Complexity: O(m * n * p) where m is the number of crimes, n is the maximum number of members, and p is the minimum profit threshold. Space Complexity: O(n * p) for storing the DP states.

Solution

The solution uses a dynamic programming approach where we create a 2D array to keep track of the number of ways to achieve various profit levels with a limited number of members. We iterate through each crime and update our DP table based on whether we choose to include the crime or not. The final answer is obtained by summing all the valid combinations that meet or exceed the minProfit.

Code Solutions

def profitableSchemes(n, minProfit, group, profit):
    MOD = 10**9 + 7
    m = len(group)
    dp = [[0] * (minProfit + 1) for _ in range(n + 1)]
    dp[0][0] = 1  # Base case: 1 way to achieve profit 0 with 0 members
    
    for i in range(m):
        g = group[i]
        p = profit[i]
        # We iterate backwards to avoid overwriting states we still need to use
        for j in range(n, g - 1, -1):
            for k in range(minProfit, -1, -1):
                dp[j][min(minProfit, k + p)] = (dp[j][min(minProfit, k + p)] + dp[j - g][k]) % MOD
                
    # Sum up all ways to achieve at least minProfit
    return sum(dp[j][minProfit] for j in range(n + 1)) % MOD
← Back to All Questions