Daily bit(e) C++. Схемы прибыли

Добавлено 24 сентября 2023 в 01:47

Daily bit(e) C++ #224, распространенная задача на собеседованиях: схемы прибыли.

Сегодня мы рассмотрим распространенную задачу на собеседованиях по C++: схемы прибыли.

Дано количество мошенников и список схем в виде двух std::vector<int>, которые представляют необходимое количество мошенников и прибыль, полученную каждой схемой. Верните количество комбинаций распределений мошенников по схемам, дающих прибыль, равную или превышающую пороговое значение profit_threshold.

Например, для входных данных: пять человек, целевая прибыль, равная 5, и схемы {3,3,2,1,2}, {1,3,2,1,2}, у нас есть три варианта: две комбинации {3 ,2}, обе из которых приводят к прибыли в размере пяти, а комбинация {2,2,1} также приводит к прибыли в размере пяти.

Прежде чем прочитать решение, советую попытаться решить задачу самостоятельно. Вот ссылка на Compiler Explorer с парой тестовых случаев: https://compiler-explorer.com/z/dPaosqvdT.

Решение

При рассмотрении отдельной схемы у нас есть только два варианта; мы можем либо взять её, либо нет. Это напрямую соответствует рекурсивному подходу сверху вниз.

В упрощенном формате мы можем рассчитать combinations(idx, remaining_people, unfulfilled_profit) как сумму:

не берем схему в idx:
combinations(idx+1, remaining_people, unfulfilled_profit)
берем схему в idx:
combinations(idx+1, remaining_people-people[idx], unfulfilled_profit-profit[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 (int i = 0; i < std::ssize(people); ++i) 
    {
        // предварительно рассчитать всех возможных
        // оставшихся людей
        for (int j = 0; j <= n; ++j) 
        {
            int remaining_people = j - people[i];
            // мы не можем использовать эту схему
            if (remaining_people < 0) 
            {
                current[j] = previous[j];
                continue;
            }

            // предварительно рассчитать все возможные
            // значения прибыли
            for (int k = 0; k <= target; ++k) 
            {
                // Прибыльно, если мы берем эту схему
                int total_profit = std::min(target, k + profit[i]);
                int count = previous[remaining_people][total_profit];
                // Если мы уже в прибыли, то в число комбинаций
                // входит и текущая ситуация.
                if (total_profit == target)
                    count = (count + 1) % MOD;
                
                // Итого: мы_взяли + мы_не_взяли
                current[j][k] = (count + previous[j][k]) % MOD;
            }
        }

        // Мы предварительно рассчитали все значения
        previous = std::move(current);
        current = std::vector<std::vector<int>>(n+1, 
            std::vector<int>(target+1,0));
    }
    // Если наша целевая прибыль равна нулю, мы также
    // должны учитывать случай, когда мы вообще не выбираем
    // какую-либо схему.
    if (target == 0)
        return (previous[n][0]+1) % MOD;
    else
        return previous[n][0];
}

Открыть решение на Compiler Explorer.

Решение

Теги