#879

Profitable Schemes

candidate master · 1475 · lc hard +32 · verified · 48.2% accepted · 1,944 likes · top 34%

Description

A criminal organization has n members and a list of potential crimes. Crime i yields profit[i] and requires exactly group[i] members to execute. Each member can participate in at most one crime.

A profitable scheme is any subset of crimes whose total profit is at least minProfit and whose total participants do not exceed n.

Return the number of profitable schemes modulo 10⁹ + 7.

Example 1:

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:

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).

Code

1

2

3

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int: