0879. Profitable Schemes¶
题目信息¶
- 题号:
0879
- 难度:
Hard
- 主题:
子集计数、人数上限、利润阈值
- 原题:
- 重点:
每项犯罪最多选择一次;合法方案是总用人数不超过 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,因此恰有一种合法方案。