0805HardArrayDynamic ProgrammingKnapsack Problem0-1 Knapsack

Counting Staffable Restoration Plans

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(k * rangers * target) for k projects, at most 100 * 100 * 100 cell updates.Space O(rangers * target) for the table of plan counts.

Keep a table of plan counts indexed by rangers committed and credits earned so far, where the credit axis stops at `target`: since anything at or beyond the target is equally worthwhile, all of those totals share the top bucket, which keeps the axis at `target + 1` entries no matter how large the credit sums grow. Start from the empty plan at (0, 0) and fold the projects in one at a time, walking the ranger axis downwards so each project is added to a plan at most once. The answer is the total sitting in the top credit bucket across every ranger count, taken modulo 1000000007.

Pythonentry point: count_restoration_plans

def count_restoration_plans(rangers, target, crew, credits):
    # Credits beyond the target buy nothing, so a running total is only ever tracked up
    # to the target and everything at or above it shares one bucket. That keeps the
    # table at (rangers + 1) x (target + 1) counts of plans; each project is folded in
    # once, walking the crew axis downwards so no project is ever used twice.
    # Time O(k * rangers * target) for k projects, space O(rangers * target).
    limit = 1000000007
    table = [[0] * (target + 1) for _ in range(rangers + 1)]
    table[0][0] = 1
    for i in range(len(crew)):
        need = crew[i]
        gain = credits[i]
        for used in range(rangers - need, -1, -1):
            source = table[used]
            sink = table[used + need]
            for earned in range(target, -1, -1):
                plans = source[earned]
                if plans:
                    landed = earned + gain
                    if landed > target:
                        landed = target
                    sink[landed] = (sink[landed] + plans) % limit
    total = 0
    for used in range(rangers + 1):
        total = (total + table[used][target]) % limit
    return total

The obvious version

Grow a dictionary from an exact (rangers committed, credits earned) pair to the number of plans that reach it, adding one project per round and dropping any plan that would outrun the rangers on hand. Nothing is bucketed, so the credit totals are kept exactly however large they get. At the end add up the plans whose exact credits reach the target.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_restoration_plans(rangers, target, crew, credits):
    limit = 1000000007
    # exact crew used and exact credits earned, no bucketing of any kind
    reached = {(0, 0): 1}
    for i in range(len(crew)):
        need = crew[i]
        gain = credits[i]
        grown = dict(reached)
        for state, plans in reached.items():
            used, earned = state
            if used + need <= rangers:
                key = (used + need, earned + gain)
                grown[key] = (grown.get(key, 0) + plans) % limit
        reached = grown
    total = 0
    for state, plans in reached.items():
        if state[1] >= target:
            total = (total + plans) % limit
    return total

How this problem was checked

Reference solution executed against 19 test cases — 19 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in