Ежедневный бит (е) 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.