Разбор задачи «Монеты для экспедиции»

Идея задачи

Нам дано n типов монет (или капсул), и каждая монета типа i имеет стоимость a_i. Монет каждого типа можно брать сколько угодно.

Нужно набрать ровно сумму S, используя минимальное количество монет.

Если это невозможно, нужно вывести -1.

Это классическая задача на динамическое программирование.

Почему задача решается через DP

Если мы хотим узнать ответ для суммы x, удобно подумать так:

• какая монета могла быть последней в оптимальном наборе?
• если последней была монета номинала c, то до этого мы должны были набрать сумму x - c
• тогда количество монет будет равно:

dp[x - c] + 1

Значит, если перебрать все возможные последние монеты, можно выбрать лучший вариант.

Состояние динамики

Обозначим:

• dp[x] — минимальное количество монет, которым можно набрать сумму x

Тогда:

• dp[0] = 0, потому что сумму 0 можно набрать без монет
• все остальные значения сначала считаем очень большими, как будто они пока недостижимы

Переход

Для каждой суммы x от 1 до S перебираем все монеты c.

Если x >= c, то можно попробовать перейти так:

dp[x] = min(dp[x], dp[x - c] + 1)

То есть:

• берём оптимальное решение для суммы x - c
• добавляем одну монету c
• сравниваем с текущим значением

Начальные значения

Удобно взять:

• INF = S + 1

Почему этого достаточно?

Потому что в худшем случае, если среди монет есть 1, ответ не может быть больше S. Значит, S + 1 — это заведомо «слишком большое» число.

Тогда:

• dp[0] = 0
• dp[1...S] = INF

После заполнения массива:

• если dp[S] == INF, то ответа нет, выводим -1
• иначе выводим dp[S]

Пример работы

Пусть:

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

Тогда:

• dp[0] = 0
• dp[1] = 1 — одна монета 1
• dp[2] = 1 — одна монета 2
• dp[3] = 2 — 1 + 2
• dp[4] = 2 — 2 + 2
• dp[5] = 1 — одна монета 5
• ...
• dp[10] = 2 — 5 + 5
• dp[11] = 3 — 5 + 5 + 1

Ответ: 3.

Почему решение правильное

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

Рассмотрим некоторую сумму x. Если её можно набрать, то в любом способе набора есть последняя монета. Пусть её номинал равен c. Тогда до неё уже была набрана сумма x - c.

Если оптимальный ответ для x - c равен dp[x - c], то, добавив монету c, получим кандидат на ответ для x, равный dp[x - c] + 1.

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

Сложность

Пусть:

• n — количество типов монет
• S — нужная сумма

Тогда:

• по времени: O(n * S)
• по памяти: O(S)

Это эффективно для стандартных ограничений этой задачи.

Реализация на C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

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

    const int INF = S + 1;
    vector<int> dp(S + 1, INF);
    dp[0] = 0;

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

    if (dp[S] == INF) {
        cout << -1 << '\n';
    } else {
        cout << dp[S] << '\n';
    }

    return 0;
}

Реализация на Python

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

INF = S + 1
dp = [INF] * (S + 1)
dp[0] = 0

for x in range(1, S + 1):
    for c in coins:
        if x >= c:
            dp[x] = min(dp[x], dp[x - c] + 1)

if dp[S] == INF:
    print(-1)
else:
    print(dp[S])

Частые ошибки

1. Путают эту задачу с задачей о количестве способов

Здесь нужно найти минимальное число монет, а не число различных наборов.

То есть переход должен быть через min, а не через сложение.

Неправильно:

dp[x] += dp[x - c];

Правильно:

dp[x] = min(dp[x], dp[x - c] + 1);

2. Неправильно выбирают бесконечность

Если поставить слишком маленькое значение вместо INF, можно случайно получить неверный ответ.

Безопасный вариант:

• INF = S + 1

3. Забывают обработать невозможный случай

Если сумма недостижима, в dp[S] так и останется INF. В этом случае надо вывести -1.

4. Ошибаются с индексами

Нужно аккуратно проверять условие x >= c, чтобы не выйти за границы массива dp.

На что обратить внимание

Эта задача — один из базовых шаблонов DP.

Очень полезно запомнить такую схему:

• dp[x] — лучший ответ для состояния x
• перебираем все переходы
• обновляем через min или max в зависимости от задачи

В этой задаче состояние — это текущая сумма, а переход — добавление одной монеты.

Возможная альтернатива

Эту задачу можно воспринимать и как поиск кратчайшего пути по состояниям:

• вершины: суммы от 0 до S
• из суммы x можно перейти в x + c
• каждый переход стоит 1

Тогда нужно найти кратчайший путь из 0 в S.

Но реализация через обычное динамическое программирование здесь проще и естественнее.

Вывод

Задача решается динамическим программированием по сумме.

Мы храним минимальное число монет для каждой суммы от 0 до S, а затем постепенно строим ответы для больших сумм через ответы для меньших.

Это стандартный и очень важный шаблон, который часто встречается в задачах на DP.