Daily bit(e) of C++ | Profitable schemes
Daily bit(e) of C++ #224, Common interview problem: Profitable schemes.
Today, we will look at a common C++ interview problem: Profitable schemes.
Given the number of grifters and a list of schemes as two std::vector<int>, that represent the number of grifters required and the profit generated by each scheme. Return the number of combinations to distribute the grifters among schemes that generate at least profit_threshold profit.
For example, for the input: five people, five target profit and the schemes {3,3,2,1,2}, {1,3,2,1,2}, we have three possibilities: two combinations of {3,2}, both leading to a profit of five and a combination of {2,2,1} also leading to a profit of five.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/dPaosqvdT.
Solution
We have only two options when considering a single scheme; we can either include it or not. This directly maps to a top-down recursive approach.
In a simplified format, we can calculate combinations(idx, remaining_people, unfulfilled_profit) as the sum of:
we don’t pick the scheme at idx:
combinations(idx+1, remaining_people, unfulfilled_profit)we pick the scheme at idx:
combinations(idx+1, remaining_people-people[idx], unfulfilled_profit-profit[idx])
There are several caveats here:
we can only pick a scheme if we have enough people: remaining_people >= people[idx]
any profit above the threshold is irrelevant; therefore we need to cap unfulfilled_profit-profit[idx] to non-negative values
trivially recursing would cause us to recompute the same suffix values over and over, so we want to cache the already computed values
This is a valid approach, but it has one downside: the time and space complexity is O(s*p*t), where s is the number of schemes, p is the number of people, and t is the profit threshold.
The important observation here is that to calculate the values for idx, we only need the values for idx+1, meaning that using a bottom-up approach, we can decrease our space complexity to O(p*t).
We can re-use the above logic; however, since we are doing a bottom-up approach, we must pre-calculate all possible p and t values at each iteration.
