0879. Profitable Schemes

题目信息

题号:

0879

难度:

Hard

主题:

子集计数、人数上限、利润阈值

原题:

LeetCode 0879

重点:

每项犯罪最多选择一次;合法方案是总用人数不超过 n 且总利润至少 minProfit 的犯罪子集,minProfit 为零时空集也计入

题目重述

有若干项可选择的犯罪活动,第 i 项需要 group[i] 名成员并产生 profit[i] 利润。共有至多 n 名可用成员,每项活动最多执行一次;所选活动需要的成员总数不能超过 n。

选择任意犯罪子集,若所需成员总数不超过 n,且利润总和至少为 minProfit,则该子集是一种盈利方案。不同活动集合视为不同方案;当 minProfit == 0 时,不选择任何活动的空子集也满足条件。请返回盈利方案数量对 10^9 + 7 取模后的结果。

1 <= n <= 100,0 <= minProfit <= 100;group.length == profit.length 且长度在 [1, 100] 范围内,1 <= group[i] <= 100,0 <= profit[i] <= 100。

自建示例

人数上限排除选择全部活动:

输入:n = 5, minProfit = 3, group = [2,2,3], profit = [2,3,4]
输出:5
解释:合法子集为 {第二项}、{第三项}、{第一项,第二项}、{第一项,第三项}、{第二项,第三项};三项全选需要 7 人,超过上限。

利润阈值为零时空集也计数:

输入:n = 1, minProfit = 0, group = [2], profit = [5]
输出:1
解释:唯一活动需要 2 人,超过可用人数,不能选择;但空子集使用 0 人且利润 0 已达到阈值 0,因此恰有一种合法方案。