@HedgeHog1234

Как это решать?

В Волшебной стране используются монетки достоинством A1, A2,..., AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные
На вход программы сначала поступает число N (1 <= N <= 109), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A1, A2,..., AM (1 <= Ai <= 109).

Выходные данные
Сначала выведите K - количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).

Примеры
входные данные
100 6
11 20 30 40 11 99
выходные данные
3
40 30 30
  • Вопрос задан
  • 238 просмотров
Решения вопроса 1
Vindicar
@Vindicar
RTFM!
1. Подумать.
2. Написать код.

А если серьёзно, задача сводится к разложению числа на заданные слагаемые. Это гуглится.
Один из способов (необязательно самый быстрый) - рекурсивное разложение. Упрощенно, перебираешь все Ai меньшие N. Выкидываешь это Ai из рассматриваемого набора, и затем рекурсивно пытаешься составить число (N - Ai) из всех Aj, меньших или равных Ai (так как большие слагаемые ты уже рассмотрел).
Углубляясь в рекурсию, рано или поздно ты наткнёшься на одну из двух ситуаций:
а) среди Aj есть число, равное искомому. Решение найдено, осталось размотать рекурсию обратно и собрать в кучку использованные Ai.
б) нет ни одного Aj, меньшего или равного искомому числу. Решения нет.
В твоём случае будет ещё случай в) Сумма всех Ai меньше N. Решения нет, заплатить не удастся. Это можно проверить вообще сразу.

Реализовать будет проще, если отсортируешь Ai в порядке убывания. Тогда вместо удаления Ai из списка слагаемых достаточно будет выбрать индекс i, с которого будешь начинать рассмотрение слагаемых - все элементы до i-го либо слишком велики, либо уже были рассмотрены и не пригодились.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Тут очень большая сумма и очень мало монет. Поэтомуэту задачу надо решать полным перебором.

Рекурсивная функция получает, например, сколько первых типов монет можно использовать и какую сумму надо набрать. Возвращает список монет. Внутри надо перебрать сколько раз последняя сонета береться: от 0 до 2 раз. Оставшаяся сумма рекурсивно собирается оставшимеся монетами (минус один к количеству типов, ведь последний мы уже использовали). Если рекурсивная функция что-то собрала, добавляем к ее ответу 0-2 теущие монеты и вощвращаем.

Это отработает за 3^15*15 = 215233605 операций. Обычно это проходит. Можно соптимизировать: не брать текущую монету, если она слишком большая, останавливать перебор, если сумма первых монет недостаточна. Ну, или соптимизировать до 2^15*15: подсчитайте все возможные суммы, если можно брать по 1 монете. Таким же перебором или вообще циклом с битовой маской. Отсортируйте список из 32 тысяч чисел и проверьте, а есть ли там 2 числа, дающие искомую сумму (двумя указателями: двинули один раз левый, двигаем правый пока сумма слишком большая).

Отдельно надо проверить, надо ли выводить -1 в ответ (сумма всех монет меньше N).
Ответ написан
Комментировать
Alexandroppolus
@Alexandroppolus
кодир
Вариант через динамическое программирование.

function bankomat(sum, coins, maxCC) {
    const full = coins.reduce((sum, c) => sum + c * maxCC, 0);
    if (full < sum) return -1;
    
    const dp = Array.from({length: sum + 1}, () => ({
        count: full + 1,
        coins: {},
    }));
    coins.sort((a, b) => a - b);
    dp[0].count = 0;
    for (let i = 1; i <= sum; ++i) {
        const item = dp[i];
        let optCoin = 0;
        for (let j = 0; j < coins.length; ++j) {
            const coin = coins[j];
            if (coin > i) break;
            const prev = dp[i - coin];
            if (item.count > prev.count + 1 && (prev.coins[coin] || 0) < maxCC) {
                item.count = prev.count + 1;
                optCoin = coin;
            }
        }
        if (optCoin) {
            const prev = dp[i - optCoin];
            item.coins = {
                ...prev.coins,
                [optCoin]: (prev.coins[optCoin] || 0) + 1
            };
        }
    }

    if (dp[sum].count > full) {
        return 0;
    }

    const arr = [];
    Object.keys(dp[sum].coins).forEach((coin) => {
        const c = dp[sum].coins[coin];
        for (let i = 0; i < c; ++i) {
            arr.push(Number(coin));
        }
    });
    return arr;
}

console.log(bankomat(100, [11, 20, 30, 40, 12, 99], 2)); // [20, 40, 40]
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы