Skip to the code
cf.
+50 XP

#516 Profitable Feature Sets

hard

A product team can build any set of candidate features this quarter. Feature i needs needs[i] engineers for the whole quarter and is expected to earn profits[i]. The team has engineers people, and an engineer can work on only one feature.

Write countFeatureSets(engineers, minProfit, needs, profits) that returns how many sets of features (including the empty set) use at most engineers people and earn at least minProfit in total. Return it modulo 1000000007.

Example 1

Input: engineers = 4, minProfit = 3, needs = [2,2], profits = [2,3]
Output: 2

Feature 1 alone (2 people, profit 3), or both features (4 people, profit 5).

Example 2

Input: engineers = 5, minProfit = 0, needs = [1,6], profits = [1,1]
Output: 2

With no profit required, the empty set and feature 0 both count. Feature 1 needs 6 people.

Constraints

  • 1 <= engineers <= 100
  • 0 <= minProfit <= 100
  • 1 <= needs.length <= 100
  • needs.length === profits.length
  • 1 <= needs[i] <= 100
  • 0 <= profits[i] <= 100
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).