task3.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cout << "Введите количество номиналов монет: ";
    cin >> n;
    vector<int> coins(n);
    cout << "Введите номиналы монет: ";
    for (int i = 0; i < n; ++i) {
        cin >> coins[i];
    }

    int sum;
    cout << "Введите сумму: ";
    cin >> sum;

    // Динамическое программирование с перебором вверх
    int max_coin = *max_element(coins.begin(), coins.end());
    int max_sum = sum + max_coin; // запас для перебора
    vector<int> dp(max_sum + 1, max_sum + 1);
    dp[0] = 0;
    for (int s = 1; s <= max_sum; ++s) {
        for (int c : coins) {
            if (s - c >= 0) {
                dp[s] = min(dp[s], dp[s - c] + 1);
            }
        }
    }

    // Ищем минимальное s >= sum, для которого есть решение
    int min_count = max_sum + 1;
    int min_sum = -1;
    for (int s = sum; s <= max_sum; ++s) {
        if (dp[s] < min_count) {
            min_count = dp[s];
            min_sum = s;
        }
    }

    if (min_sum == sum) {
        cout << "Минимальное количество монет для суммы " << sum << ": " << min_count << endl;
    } else if (min_sum > sum && min_sum != -1) {
        cout << "Минимальное количество монет для суммы " << sum << ": " << min_count << endl;
    }

    return 0;
}