<jupyter_start><jupyter_text>说明：    有一组G成员，以及他们可能犯下的各种罪行。    第i种犯罪产生 利润 profit[i]，并要求团体 group[i] 成员参与。    如果成员参与一项犯罪，则该成员不能参与另一项犯罪。    让我们将这些犯罪的任何子集至少产生P利润，并将参与该犯罪子集的成员总数最多为G称为有利可图的方案。    可以选择多少种方案？    由于答案可能非常大，因此请以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 group 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 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). 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<jupyter_code>class Solution:
    def profitableSchemes(self, G: int, P: int, group, profit) -> int:
        # 一共有 G 个人，P 是至少获得利润
        # group是参与某个犯罪，需要参与人的数量
        # profit是某项犯罪所获得的利润
        
        max_val = pow(10, 9) + 7
        
        dp = [[0] * (P + 1) for _ in range(G + 1)]
        
        for i in range(len(profit)):
            pro = profit[i]
            gro = group[i]
            
            for i in range(G, -1, -1):
                for j in range(P, -1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - pro][j - gro] + 1)
        
        print(dp)
        return dp[-1][-1]
class Solution:
    def profitableSchemes(self, G: int, P: int, group, profit) -> int:
        # 一共有 G 个人，P 是至少获得利润
        # group是参与某个犯罪，需要参与人的数量
        # profit是某项犯罪所获得的利润
        
        max_val = pow(10, 9) + 7
        
        dp = [[0] * (P + 1) for _ in range(G + 1)]
        new_dp = [[0] * (P + 1) for _ in range(G + 1)]
        dp[0][0] = 1
        new_dp[0][0] = 1
        
        
        for i in range(len(profit)):
            gro = group[i]
            pro = profit[i]

            for i in range(G + 1):
                for j in range(P + 1):
                    g = i + gro
                    if g <= G:
                        p = min(P, j + pro)
                        new_dp[g][p] += dp[i][j]
            dp = new_dp
        
        res = 0
        for i in range(G + 1):
            res += dp[i][P] 
        return res % max_val
class Solution:
    def profitableSchemes(self, G: int, P: int, group, profit) -> int:
        # 一共有 G 个人，P 是至少获得利润
        # group是参与某个犯罪，需要参与人的数量
        # profit是某项犯罪所获得的利润
        
        max_val = pow(10, 9) + 7
        
        dp = [[0] * (P + 1) for _ in range(G + 1)]
        dp[0][0] = 1
        for i in range(len(group)):
            gro = group[i]
            pro = profit[i]
            
            for i in range(G - gro, -1, -1):
                for j in range(P, -1, -1):
                    p = min(P, pro + j)
                    g = i + gro
                    dp[g][p] += dp[i][j]
        
        res = 0
        for i in range(G + 1):
            res += dp[i][P]
        return res % max_val
class Solution:
    def profitableSchemes(self, G: int, P: int, group, profit) -> int:
        # 一共有 G 个人，P 是至少获得利润
        # group是参与某个犯罪，需要参与人的数量
        # profit是某项犯罪所获得的利润
        
        max_val = pow(10, 9) + 7
        
        dp = [[0] * (P + 1) for _ in range(G + 1)]
        dp[0][0] = 1
        new_dp = [[0] * (P + 1) for _ in range(G + 1)]
        new_dp[0][0] = 1
        
        for k in range(len(group)):
            gro = group[k]
            pro = profit[k]
            
            for i in range(G + 1):
                for j in range(P + 1):
                    p = min(P, pro + j)
                    g = i + gro
                    if g <= G:
                        new_dp[g][p] += dp[i][j]
            dp = new_dp
            
        res = 0
        for i in range(G + 1):
            res += dp[i][P]
        return res % max_val
solution = Solution()
solution.profitableSchemes(10, 5, [2, 3, 5], [6, 7, 8])
    [[0, 0, 0, 0], 
     [0, 0, 0, 0], 
     [0, 0, 0, 0], 
     [0, 0, 0, 0], 
     [0, 0, 0, 0], 
     [0, 0, 0, 0]]<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13973589435774308, 'fraction_numerical': 0.04081632653061224, 'mean_word_length': 1.3417650365373806, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '518069', 'license': 'Apache-2.0', 'n_tokens_mistral': 1842, 'n_tokens_neox': 1721, 'n_words': 450, 'path': 'Dynamic Programming/1009/879. Profitable Schemes.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '4165'}