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

Question

[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

Comments

[kalapanga]

Условие и пример не соответствуют друг другу:

далее M попарно различных чисел

11 20 30 40 11 99

Answer 1

[Vindicar]

1. Подумать.
2. Написать код.

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

Реализовать будет проще, если отсортируешь Ai в порядке убывания. Тогда вместо удаления Ai из списка слагаемых достаточно будет выбрать индекс i, с которого будешь начинать рассмотрение слагаемых - все элементы до i-го либо слишком велики, либо уже были рассмотрены и не пригодились.

Comments

[Rsa97]

Тут ситуация чуть усложняется - надо найти наименьшее количество монет. Значит стоит добавить ограничение на глубину рекурсии, чтобы не искать варианты, где монет столько же или больше, чем в минимальном уже найденном варианте. И не останавливаться на первом найденном варианте, а продолжать поиск, пока не будет найден вариант из одной монеты или на первом уровне рекурсии сумма оставшихся Aj не станет меньше N.
Пример:
N = 60
A = [40, 40, 30, 30, 10, 10]
Первым будет найден вариант [40, 10, 10], а нужен [30, 30].

[HedgeHog1234]

Я так и делал, только в строчке

def main(n, d):
    if n in d:  #тут
        return n

Вылезает ошибка builtins.TypeError: argument of type 'NoneType' is not iterable. Я не понимаю почему.

n, m = map(int, input().split())
a = list(map(int, input().split()))
s = []
for i in a:
    s.append(i)
    s.append(i)
    
s.sort()
    
def main(n, d):
    if n in d:
        return n
    if d[0] > n:
        return -1
    for i in d:
        f = []
        if i > n:
            break
        else:
            k = d
            u = main(n-d[i],k.remove(d[i]))
            if u != -1:
                return [u].append(d[i])

    return -1

if s[0] > n:
    print(-1)
else:
    print(main(n,s))

[Vindicar]

HedgeHog1234, у тебя d в какой-то момент времени оказывается None.
Я подозреваю, что это потому что ты делаешь вызов
u = main(n-d[i], k.remove(d[i]))
В d присвоится значение, возвращённое k.remove(d[i]). Ты думаешь, что remove() возвращает копию списка без указанного элемента? Ты ошибаешься, remove() изменяет список на месте (т.е. он останется изменённым после возврата из рекурсии) и возвращает None.

Перечитай мой совет насчёт сортировки. Так реально будет проще.

Answer 2

[Wataru]

Тут очень большая сумма и очень мало монет. Поэтомуэту задачу надо решать полным перебором.

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

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

Отдельно надо проверить, надо ли выводить -1 в ответ (сумма всех монет меньше N).

Answer 3

[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]

Comments

[Wataru]

Там ограничения: сумма до миллиарда, 15 типов монет. Это ДП тут не подходит.

[Alexandroppolus]

Wataru, да, для миллиарда это будет тяжеловато и лучше перебором. Но, например, для 100000 и 15 монет выйдет определенно быстрее. Возможно, наилучшим вариантом будет выбор стратегии в зависимости от значений.

в ДП меня смущает такой кейс: для dp[sum] единственным оптимальным предшественником оказался dp[sum - k], но в составе dp[sum - k] монета с номиналом k использована дважды, хотя этот dp[sum - k] можно было бы собрать и по другому с тем же количеством монет, сэкономив хотя бы одну монету k. Мне не удалось придумать такой пример, но нет гарантии, что такой кейс невозможен

[Wataru]

Alexandroppolus, Вообще, да, странное у вас ДП. По идее, ДП должно быть двумерное: F(sum, k) - минимальное количество монет, чтобы собрать сумму sum, используя первые k монет (где все монеты имеют по 2 копии и можно их использовать только по одному разу). Это стандартное ДП и можно хранить только одну строчку, если пересчитывать ее с конца: dp[i] = min(dp[i], dp[i-coin_value]). Но тогда цикл по монеткам должен быть внешним.

У вас же параметр только один, а использованные монеты засунуты в возвращаемое значение. Так делать нельзя. Любое состояние, влияющее на ответ должно быть в параметрах, а не в вычисляемом значении.
Указанная вами проблема действительно существует. При чем, не надо чтобы единственным предшественником был dp[sum-k]. Достаточно, чтобы по всем возможным оптимальным предшественникам нужная монета была использованна дважды.

Я тоже пока тест придумать не могу, но пока алгоритм не доказан - он должен считаться неправильным. Ваш алгоритм не является ДП как таковым, ибо по указанной проблеме, нельзя решать задачу для n через n-k: Ибо оптимальное решение для подзадачи не гарантирует оптимальное решение для текущей задачи. Так что его надо как-то по-другому доказывать.

Можно попробовать стресс тест написать с нормальным ДП или перебором: Авось рандом тест найдет.