Ежедневный бит (е) C ++ # 224, Распространенная задача на собеседовании: прибыльные схемы.
Сегодня мы рассмотрим распространенную проблему интервью C++: прибыльные схемы.
Учитывая количество мошенников и список схем в виде двух std::vector‹int›, которые представляют необходимое количество мошенников и прибыль, полученную от каждой схемы. Возвращает количество комбинаций, чтобы распределить мошенников по схемам, которые приносят не менее profit_threshold прибыли.
Например, для ввода: пять человек, пять целевых профитов и схемы {3,3,2,1,2}, {1,3,2,1,2}, у нас есть три возможности: две комбинации {3,2}, каждая из которых дает прибыль в размере пяти, и комбинация {2,2,1} также приводит к прибыли в размере пяти.
Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/dPaosqvdT.
Решение
У нас есть только два варианта при рассмотрении одной схемы; мы можем либо включить его, либо нет. Это напрямую соответствует рекурсивному подходу сверху вниз.
В упрощенном формате мы можем рассчитать комбинации(idx, rest_people, unfulfilled_profit) как сумму:
- мы не выбираем схему на idx:
комбинации(idx+1, оставшиеся_люди, невыполненная_профит) - выбираем схему в idx:
комбинации(idx+1,оставшиеся_люди-люди[idx],нереализованная_прибыль-прибыль[idx])
Здесь есть несколько предостережений:
- мы можем выбрать схему, только если у нас достаточно людей: remaining_people ›= people[idx]
- любая прибыль выше порога не имеет значения; поэтому нам нужно ограничить unfulfilled_profit-profit[idx] неотрицательными значениями.
- тривиальная рекурсия заставит нас повторно вычислять одни и те же значения суффикса снова и снова, поэтому мы хотим кэшировать уже вычисленные значения
Это допустимый подход, но у него есть один недостаток: сложность времени и пространства составляет O(s*p*t), где s — количество схем, p — количество людей, а t — порог прибыли.
Важным замечанием здесь является то, что для вычисления значений idx нам нужны только значения для idx+1, а это означает, что, используя восходящий подход, мы можем уменьшить сложность пространства до O(p*t).
Мы можем повторно использовать приведенную выше логику; однако, поскольку мы используем восходящий подход, мы должны предварительно вычислить все возможные значения p и t на каждой итерации.
inline constexpr int MOD = 1e9 + 7; int scheme_combinations(int n, int target, const std::vector<int>& people, const std::vector<int>& profit) { std::vector<std::vector<int>> previous( n+1,std::vector<int>(target+1,0)); auto current = previous; // for every prefix for (int i = 0; i < std::ssize(people); ++i) { // precalculate all possible remaining people for (int j = 0; j <= n; ++j) { int remaining_people = j - people[i]; // we can't run this scheme if (remaining_people < 0) { current[j] = previous[j]; continue; } // precalculate all possible profit values for (int k = 0; k <= target; ++k) { // Profit if we do pick this scheme int total_profit = std::min(target, k + profit[i]); int count = previous[remaining_people][total_profit]; // If we are already at profit, the number of // combinations includes the current situation as well. if (total_profit == target) count = (count + 1) % MOD; // The total is: we_pick + we_dont_pick current[j][k] = (count + previous[j][k]) % MOD; } } // We have precalculated all values, flip previous = std::move(current); current = std::vector<std::vector<int>>(n+1, std::vector<int>(target+1,0)); } // If our target profit is zero, we also have to count the case // when we do not pick any scheme at all. if (target == 0) return (previous[n][0]+1) % MOD; else return previous[n][0]; }
Откройте решение в Compiler Explorer.