Solution
Approach 1: Dynamic Programming
Intuition
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 P
dollars.
Algorithm
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 cur2
.
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
.
Complexity Analysis
-
Time Complexity: , where is the number of crimes available to the gang.
-
Space Complexity: .
Analysis written by: @awice.