Approach 1: Dynamic Programming
We don't care about the profit of the scheme if it is , because it surely will be over the threshold of profitability required. Similarly, we don't care about the number of people required in the scheme if it is , since we know the scheme will be too big for the gang to execute.
As a result, the bounds are small enough to use dynamic programming. Let's keep track of
cur[p][g], the number of schemes with profitability and requiring gang members: except we'll say (without changing the answer) that all schemes that profit at least
P dollars will instead profit exactly
Keeping track of
cur[p][g] as defined above, let's understand how it changes as we consider 1 extra crime that will profit
p0 and require
g0 gang members. We will put the updated counts into
For each possible scheme with profit
p1 and group size
g1, that scheme plus the extra crime (
p0, g0) being considered, has a profit of
p2 = min(p1 + p0, P), and uses a group size of
g2 = g1 + g0.
Time Complexity: , where is the number of crimes available to the gang.
Space Complexity: .
Analysis written by: @awice.