Разбор задачи «Чайная лавка мастера смесей»

Идея задачи

Нужно посчитать количество различных способов собрать набор ровно на S граммов, если есть n видов чая с фиксированными весами порций, и каждую порцию можно брать неограниченное число раз.

Ключевая особенность задачи в том, что порядок выбора порций не важен. Это значит, что наборы

• 1 + 2 + 2
• 2 + 1 + 2
• 2 + 2 + 1

считаются одним и тем же способом.

Именно поэтому здесь не подойдет наивный перебор всех последовательностей. Нужно считать комбинации, а не перестановки.

Наблюдение

Пусть dp[x] — количество способов собрать ровно x граммов.

Тогда:

• dp[0] = 1, потому что массу 0 можно получить одним способом: ничего не взять;
• для каждой порции веса coin можно попробовать добавить ее ко всем уже достижимым массам.

Если мы уже знаем число способов собрать x - coin граммов, то, добавив одну порцию веса coin, получим способ собрать x граммов.

Отсюда переход:

dp[x] += dp[x - coin]

Но очень важно правильно организовать циклы.

Почему порядок циклов важен

Если перебирать сначала сумму, а внутри — все номиналы, то одинаковые наборы начнут считаться несколько раз в разном порядке.

Нам нужно считать именно комбинации, поэтому внешний цикл должен идти по видам порций:

1. берем очередной вес порции;
2. обновляем все суммы от этого веса до S.

Тогда каждый способ будет строиться в фиксированном порядке по типам порций, и дубликатов не появится.

Формула динамики

Инициализация:

 dp[0] = 1

Переход для каждой порции веса coin:

for x from coin to S:
    dp[x] += dp[x - coin]

Ответ: dp[S].

Разбор на примере

Пусть:

S = 5
coins = [1, 2, 5]

Изначально:

dp = [1, 0, 0, 0, 0, 0]

После обработки веса 1

Любую сумму от 1 до 5 можно набрать только единицами:

dp = [1, 1, 1, 1, 1, 1]

После обработки веса 2

• dp[2] += dp[0], теперь сумму 2 можно набрать еще и одной двойкой;
• dp[3] += dp[1], сумму 3 можно набрать как 1 + 2;
• dp[4] += dp[2], сумму 4 можно набрать как 2 + 2 и другими способами;
• dp[5] += dp[3], сумму 5 можно дополнить двойкой к способам для 3.

После этого количество способов увеличится.

После обработки веса 5

Добавится еще один способ: взять одну порцию веса 5.

Итоговый ответ будет равен 4.

Почему это корректно

Докажем идею перехода.

Пусть мы обрабатываем некоторый вес coin.

В этот момент dp[x] хранит количество способов собрать x граммов, используя только уже рассмотренные типы порций.

Когда мы делаем

dp[x] += dp[x - coin]

мы добавляем ко всем способам собрать x - coin граммов еще одну порцию веса coin. Так получаются все способы собрать x граммов, в которых последняя добавленная порция имеет вес coin.

Так как типы порций рассматриваются по очереди, один и тот же набор не может быть посчитан дважды в разных порядках.

Значит, после обработки всех типов порций массив dp содержит правильные значения, а dp[S] — правильный ответ.

Оценка сложности

Пусть n — число видов порций, а S — нужная масса.

Тогда:

• время работы: O(n * S);
• память: O(S).

Это существенно лучше, чем любые полные переборы, и подходит для ограничений задачи.

Типичные ошибки

1. Неправильный порядок циклов

Вот такой код считает не комбинации, а упорядоченные способы:

for (int x = 1; x <= S; x++) {
    for (int coin : coins) {
        if (x >= coin) dp[x] += dp[x - coin];
    }
}

Он переучитывает одинаковые наборы в разных порядках.

2. Неверная база

Если забыть написать

dp[0] = 1

то динамика вообще не начнет работать: все значения останутся нулевыми.

3. Использование слишком маленького типа

Так как число способов может быть большим, в C++ лучше использовать long long.

Эталонное решение на C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int amount, n;
    cin >> amount >> n;

    vector<int> coins(n);
    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }

    vector<long long> dp(amount + 1, 0);
    dp[0] = 1;

    for (int coin : coins) {
        for (int s = coin; s <= amount; s++) {
            dp[s] += dp[s - coin];
        }
    }

    cout << dp[amount] << '\n';
    return 0;
}

Эталонное решение на Python

amount, n = map(int, input().split())
coins = list(map(int, input().split()))

dp = [0] * (amount + 1)
dp[0] = 1

for coin in coins:
    for s in range(coin, amount + 1):
        dp[s] += dp[s - coin]

print(dp[amount])

Пояснение к коду

Что хранится в dp

dp[s] — это количество способов собрать ровно s граммов с помощью уже обработанных видов чая.

Почему внутренний цикл идет слева направо

Мы решаем задачу с неограниченным числом порций каждого вида. Поэтому, когда обрабатываем очередной вес coin, мы должны разрешать использовать его несколько раз. Именно для этого суммы перебираются по возрастанию.

Если бы каждый вес можно было взять только один раз, пришлось бы идти справа налево.

Что нужно запомнить

Эта задача — классический пример динамики на подсчет числа способов в модели «неограниченный набор предметов».

Полезный шаблон:

• dp[0] = 1;
• внешний цикл по предметам;
• внутренний цикл по сумме слева направо;
• переход dp[x] += dp[x - w].

Если запомнить именно эту схему и понимать, почему порядок циклов влияет на то, считаем ли мы комбинации или перестановки, то такие задачи будут решаться очень уверенно.