Show problems as
Classic problem #879HardArrayDynamic ProgrammingKnapsack Problem0-1 Knapsack

Profitable Schemes

Real-world version: Counting Staffable Restoration Plans
Tracked in this browser only
Read Profitable Schemes on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A conservation trust has rangers field staff available for the season and a shortlist of restoration projects. Project i needs crew[i] rangers assigned to it for the whole season and, if it runs, earns the trust credits[i] habitat credits.

A plan is any set of projects chosen from the shortlist. A ranger assigned to one project cannot help with another, so a plan is workable only when the crew sizes of the projects in it add up to at most rangers. A plan is worthwhile only when the credits of the projects in it add up to at least target; overshooting target is perfectly fine and earns the plan no special standing, it just has to get there.

Count the plans that are both workable and worthwhile. The empty plan counts as a plan: it uses no rangers and earns no credits. Two plans are different when they are made of different projects, even if those projects happen to need the same crew and earn the same credits.

The count can be enormous, so return it modulo 1000000007.

Examples

Example 1

Input
rangers = 6, target = 4, crew = [2, 3], credits = [4, 4]
Output
3

The empty plan earns no credits and so falls short of the target of 4. Project 0 on its own uses 2 rangers for 4 credits, project 1 on its own uses 3 rangers for 4 credits, and both together use 5 of the 6 rangers for 8 credits, so three plans are both workable and worthwhile.

Example 2

Input
rangers = 4, target = 0, crew = [3, 2], credits = [1, 0]
Output
3

With a target of 0 every plan is worthwhile, so only the ranger count matters. The empty plan, project 0 alone at 3 rangers and project 1 alone at 2 rangers all fit, while the two together would need 5 rangers, one more than the trust has.

Example 3

Input
rangers = 4, target = 20, crew = [1, 1], credits = [7, 8]
Output
0

Running both projects uses 2 of the 4 rangers and earns 7 + 8 = 15 credits, which is still short of the target of 20, so no plan is worthwhile.

Constraints

  • 1 <= rangers <= 100
  • 0 <= target <= 100
  • 1 <= crew.length <= 100
  • 1 <= crew[i] <= 100
  • credits.length == crew.length
  • 0 <= credits[i] <= 100
  • The answer is reported modulo 1000000007.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_restoration_plans(rangers: int, target: int, crew: list[int], credits: list[int]) -> int:
Java
public int countRestorationPlans(int rangers, int target, int[] crew, int[] credits)

More on the same topics