Как автомат с едой рассчитывает сдачу

ЗАДАНИЕ 3 (обяз. минимум)
В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен. Помогите Национальному банку решить эту задачу.
Входные данные
Первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x1, x2, ..., xN, не превосходящих 106 — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 106 —сумму, которую необходимо выдать.
Выходные данные
Программа должна количество банкнот в разложении. Если такое представление не существует, то программа должна вывести строку «No solution».

№3087 – ЧАСТЬ 1
Решение

Задание 3
Пример:
n = 5 (количество купюр)
X = {32, 12, 7, 3, 1, 5}
s = 40

Задание 3
Пример:
n = 5 (количество купюр)
X = {32, 12, 7, 3, 1, 5}
s = 40
Ваш ответ?

Задание 3
Пример:
n = 5 (количество купюр)
X = {32, 12, 7, 3, 1, 5}
s = 40
Ответ: 3, т.к. 40 = 3 + 5 + 32

Задание 3
Заведём массив Ans размера s (динамически).
Ans[i] - количество банкнот, необходимых для выдачи суммы i.

Задание 3
Заведём массив Ans размера s (динамически).
Ans[i] - количество банкнот, необходимых для выдачи суммы i.
Пример:
n = 5 (количество купюр)
X = {32, 12, 7, 3, 1, 5}
s = 40
Ans[1] = ?

Задание 3
Заведём массив Ans размера s (динамически).
Ans[i] - количество банкнот, необходимых для выдачи суммы i.
Пример:
n = 5 (количество купюр)
X = {32, 12, 7, 3, 1, 5}
s = 40
Ans[1] = 1

Задание 3
Заведём массив Ans размера s (динамически).
Ans[i] - количество банкнот, необходимых для выдачи суммы i.
Пример:
n = 5 (количество купюр)
X = {32, 12, 7, 3, 1, 5}
s = 40
Ans[1] = 1
Ans[9] = ?

Задание 3
Заведём массив Ans размера s (динамически).
Ans[i] - количество банкнот, необходимых для выдачи суммы i.
Пример:
n = 5 (количество купюр)
X = {32, 12, 7, 3, 1, 5}
s = 40
Ans[1] = 1
Ans[9] = 3

Задание 3
Заведём массив Ans размера s (динамически).
Ans[i] - количество банкнот, необходимых для выдачи суммы i.
Пример:
n = 5 (количество купюр)
X = {32, 12, 7, 3, 1, 5}
s = 40
Где будет находиться ответ?

Задание 3
Заведём массив Ans размера s (динамически).
Ans[i] - количество банкнот, необходимых для выдачи суммы i.
Пример:
n = 5 (количество купюр)
X = {32, 12, 7, 3, 1, 5}
s = 40
Где будет находиться ответ?
- В Ans[40]

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Будем заполнять Ans последовательно…

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Допустим мы уже заполнили 5 ячеек.

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Допустим мы уже заполнили 5 ячеек.

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Заполним 6-ую. Пока напишем туда какое-нибудь большое число (мы же минимум ищем)

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Заполним 6-ую. Если в конце оно там так и останется, значит, разменять эту сумму нельзя.

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Заполним 6-ую. 41 – достаточно большое число (точно не встретится потом)

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Купюру 32 мы не можем использовать

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Купюру 12 мы не можем использовать

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Купюру 7 мы не можем использовать

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Если мы используем купюру 3, то останется разменять 6 – 3 = 3 рубля. В массиве Ans уже записано, сколько потребуется купюр для этого

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Если мы используем купюру 3, то останется разменять 6 – 3 = 3 рубля. В массиве Ans уже записано, сколько потребуется купюр для этого

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Если мы используем купюру 3, то останется разменять 6 – 3 = 3 рубля. В массиве Ans уже записано, сколько потребуется купюр для этого. Итого 6 = 3 + 3, т.е. потребуется 2 купюры. Это лучше, чем было.

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Если вместо этого мы используем купюру 1, то останется разменять 6 – 1 = 5 рублей.

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Если вместо этого мы используем купюру 1, то останется разменять 6 – 1 = 5 рублей. В табличке записано, сколько купюр для этого потрбуется

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Итого, 6 = 1 + 5, т.е. потребуется 2 купюры. Такой результат уже был, ничего менять не будем.

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Если мы используем 5 рублей, то остается 6 – 5 = 1. Итого 1 + 1 = 2 купюры. Ничего не меняем.

Задание 3
Пример:
X = {32, 12, 7, 3, 1, 5}
Итого Ans[6] = 2

Подсказки
Алгоритм:
Вычислить последовательно ответ для всех возможны сумм от 1 до s:
Для каждой суммы перебрать все купюры:
Если купюра может участвовать в размене:
Посчитать, сколько купюр понадобится с её использованием (см предыдущие результаты)
Если это лучше, тем текущий результат, изменить текущий результат.

Следующее задание
Задание 4. Программа должна найти представление числа S виде суммы слагаемых из множества xi, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести строку “No solution”.
(№ 3087 на http://informatics.mccme.ru)

РЕШЕНИЕ
Заведем дополнительный массив Parent
Помимо лучшего результата (количества купюр) будем хранить какую купюру мы взяли, чтобы этот результат получить.
Ans
Parent

РЕШЕНИЕ
Заведем дополнительный массив Parent
Помимо лучшего результата (количества купюр) будем хранить какую купюру мы взяли, чтобы этот результат получить.
Ans
Parent

РЕШЕНИЕ
После вычисления, будем выводить по очереди купюры.
Начнем с 6. Видим, что нам нужна купюра 3. Выводим ее на экран.
Ans
Parent

РЕШЕНИЕ
После вычисления, будем выводить по очереди купюры.
Начнем с 6. Видим, что нам нужна купюра 3. Выводим ее на экран.
Ans
Parent
Вывод: 3

РЕШЕНИЕ
После вычисления, будем выводить по очереди купюры.
Сдвинемся на 6 – 3= 3 и выведем, соответственно, 3
Ans
Parent
Вывод: 3 3