Сколько всего способов получить 17 рублей монетами

Как сколотить состояние на современных редких монетах

Недавно один из региональных банков объявил акцию: с 17 января по 17 июля 2011 года за одну монету номиналом один, два и пять рублей, отчеканенную на Санкт-Петербургском монетном дворе в 2003 году, заплатим пять тысяч рублей.

Приятная мелочь

Акция спровоцировала ажиотаж. Если в поисковой строке любого из популярных интернет-поисковиков набить слово «монеты», то робот заботливо выдаст подсказку: «. 2003 года стоимость». Только в Яндексе число таких запросов-ответов за несколько дней приблизилось к миллиону.

Народ массово проверяет мелочь в карманах и кошельках в надежде найти ценные монеты. Разгораются нешуточные страсти: особо любознательные на нумизматических рынках и форумах выяснили, что обещанные 5 тысяч рублей за монету — форменный грабеж. Их стоимость значительно выше.

— На самом деле до упомянутой акции такие монеты в наших кругах продавались примерно за 6-9 тысяч рублей, — комментирует ситуацию московский нумизмат Александр. — Сегодня о рыночной цене говорить сложно, из-за предложения екатеринбургского СКБ-банка возник ажиотаж, такие монеты почти не продают.

На торговых площадках форума «нумизмат.ру» удалось найти только два предложения. Монету достоинством один рубль 2003 года питерской чеканки неделю назад выставили за 13 тысяч, пару дней покупателя не было, и владелец снизил цену. Ушла за 11 тысяч.

А вот монета в 5 рублей подвисла. Выставлена за 8 тысяч, сейчас продавец «упал» до 6 тысяч.

Нумизматическая ценность трех монет указанного года и двора прямо противоположна номиналу. Самые дорогие на рынке — однорублевые, при условии отличного состояния и удачном стечении обстоятельств за такую можно выручить до 15-16 тысяч рублей (по слухам, были единичные случаи продаж за 30 тысяч). Два рубля — 10 -12 тысяч. Рыночная цена пяти рублей примерно соответствует сумме, объявленной банком.

Почему в такой цене именно питерские монеты и именно 2003 года? Все до банальности просто: в том году мелочи выпустили мало, отсюда и ажиотаж.

Среди нумизматов ходят слухи, что ММД (Московский монетный двор) тоже что-то чеканил, но найти их монеты почти нереально и стоят они заоблачных денег.

Раритетом стали только металлические рубли 2003 года. Копеек тогда отчеканили много, и они ничего не стоят. Что породило малопонятный для обывателя парадокс: за пару 50-копеечных монет 2003 года вы сможете купить в лучшем случае школьную тетрадку. За рубль того же года и двора — слетаете на Канары.

С магнитом в копилку

Какая еще «мелочь» может сделать вас богачом?

Издеваться не будем: нет смысла советовать поискать в бабушкином сундуке «Рубль Константина» 1825 года, которых в мире всего шесть (на аукционах цена доходит до 550 тысяч долларов). А самая дорогая российская монета — пробный рубль «Анна с цепью» 1730 года (700 тысяч долларов).

А из реальных денег в цене две копейки 1925 года, серебро 1931 года, монеты 1947 и 1958 года. За монету номиналом пять копеек 1990 года Московского монетного двора можно выручить до пяти тысяч рублей. 20 копеек 1991 года без обозначения производителя принесут обладателю 15-17 тысяч.

20 рублей 1993 года ленинградского двора из немагнитного сплава — абсолютный раритет, 90-100 тысяч у вас в кармане.

И многие монеты 2001 года считаются раритетными. Большая редкость монеты номиналом 50 копеек, один и два рубля.

50 копеек 2001 года Московского монетного двора продают за 100 тысяч рублей, монета номиналом пять рублей чеканки 1999 года стоит от 200 до 400 тысяч рублей.

Откуда такие фантастические цены? Производство монет в те годы было сведено к минимуму. К тому же в Москве монету достоинством пять рублей в 2001-м вообще официально не чеканили. Откуда тогда взялся раритет? По слухам, произвели несколько десятков штук «пробных» монет. За ними-то коллекционеры и гоняются.

Так называемые юбилейные не в особой цене, но, скажем, за двухрублевую монетку с портретом Гагарина 2001 года можно выручить 3-4 тысячи рублей.

И вообще, есть очень много нюансов, порой совершенно ошеломительных для ненумизматов. Монета номиналом 10 рублей 1993 года ленинградского монетного двора может стоить 30-35 тысяч рублей, а может и на порядок дешевле. Все дело в сплаве, из которого она изготовлена. Если у вас есть такая и она не реагирует на магнит — вы богач. Если магнитится, то не повезло, такие у нумизматов не в цене.

Говоря о ценах, нужно понимать, что вся информация относительна. Журналисты обожают упрощать факты и округлять цены. Но рынок есть рынок, и нет гарантии, что вы такие раритеты сможете продать или купить в указанном ценовом диапазоне.

Доходит до курьезов. Некоторые банки вывешивают циничные прайсы-предложения. Вот пример: серебряную монету номиналом 100 рублей исторической серии «Калмыкия» вам продадут за 59 тысяч рублей. А вот купит ее у вас банк строго по номиналу: ровно за 100 рублей.

Если вы только вчера зарегистрировались на форуме нумизматов, то вряд ли кто-то станет вообще у вас виртуально покупать монеты. Где гарантия, что вы не мошенник? И продавать свой раритет придется через антикварный магазин, то есть с большими издержками на экспертизу и комиссию.

Профи советуют дилетантам соблюдать особую осторожность при личных встречах с покупателем. А пенсионерам и блондинкам лучше смириться с потерями и воспользоваться безопасными вариантами вроде антикварных лавок и банков, скупающих монеты.

И еще. Прежде чем избавляться от ценных монет, хорошенько подумайте: а стоит ли? Они ведь с каждым годом не дешевеют, а совсем даже наоборот.

За пруф медяков

Наряду с редкостью на стоимость монеты влияет физическое состояние. Сегодня применяются две системы оценки. По одной степень изношенности металлических денег разделена на семь степеней, по другой износ определяется по 70-балльной шкале (система доктора Уильяма Шелдона). 70 баллов присуждают свежеотчеканенной монете, 1 балл получают безнадежно убитые временем или неудачной чисткой деньги с неразличимыми деталями чеканки.

Полезный совет домохозяйкам: если вы нашли в кошельке вожделенную монетку, не надо проводить предпродажную подготовку, как-то: шкурить ее наждачкой, оттирать губкой для мытья посуды или полировать пастой гои. Дилетант может дошлифовать до состояния, после которого монету не продать даже по номиналу.

А идеальная монета на сленге нумизматов называется proof. Правда, это не степень сохранности, а технология производства. Такие монеты производитель полирует до зеркального блеска, четко прорабатывает все детали рисунка. В принципе, их даже брать в руки можно только в полотняных перчатках. Оплатить покупку в магазине пруф-монетами гипотетически можно, но не нужно. В принципе, обычному человеку пруф и не должна попасть в руки. Но если все-таки попадет, то не вздумайте хранить ее в кошельке с другой мелочью: неизбежные царапины убьют ее коллекционную стоимость. Будет вам тогда не пруф — во всех смыслах.

Как оценить монету

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

Лучший: сфотографировать в режиме макросъемки и разместить на одном из форумов нумизматов. Только сформулируйте вопрос о ее стоимости вежливо, и о монете знатоки вам все расскажут.

Орел или решка

Какая у монеты сторона лицевая, а какая — наоборот?

Принято считать аверсом (от латинского «обращенный лицом») ту сторону монеты, на которой указан банк, изображен глава государства. На аверсе современных российских рублей изображен герб России, на копейках — святой Георгий Победоносец. Соответственно, реверс (обратная сторона) там, где номинал монеты.

Правило не действует в отношении памятных десятирублевых монет. Там все с точностью до наоборот: на этих главная сторона та, где указана стоимость.

Олимпиадное хобби. Размен монет

Привет. Сегодня понедельник, поэтому я решил, что стоит начать свой рабочий день с разогрева пальцев и мозга. Для тех кто не в курсе: мое олимпиадное хобби состоит в решении олимпиадных задач по программированию, которые я беру с сайта http://uva.onlinejudge.org/. Сегодня нам предстоит решить задачу о размене монет из области динамического программирования. Задача не очень сложная, но есть над чем поразмыслить, поэтому заинтересовавшихся прошу под кат. К слову, это третья наша задача, но, безусловно, из всех самая интересная.

Небольшое лирическое отступление.

Мой программистский путь начался далеко не в 3 года, когда многие будущие программисты уже разбирали калькулятор и делали из него компьютер. Я начал заниматься программированием в школе в 8 классе. К слову сказать, моя школа была далека от технического направления, поэтому в своих начинаниях я был почти одинок. Но, благодаря директору нашей школы, у нас был «кружок» по программированию, где мы готовились к школьной олимпиаде по программированию. Нас там было не более трех человек единовременно, но нашего преподавателя, к счастью, это не расстраивало. Моим преподавателем программирования был Кавокин А.А., отчасти благодаря ему я и встал на столь удивительный путь программиста. Так вот, каждый урок наш наставник начинал с логической задачки, чтобы мы расшевелили свои извилины. Это мне настолько нравилось в школе, что я решил вас тоже так помучить, поэтому сегодня мы начнем с небольшой логической задачки, которая поможет нам размяться.

Логическая задачка для разминки:

В нашем городе проезд в общественном транспорте оплачивается непосредственно во время поездки, для чего по автобусу курсирует кондуктор, собирая со всех плату за проезд. Стоимость билета составляет 20 рублей. Однажды, на одной из остановок в автобус зашли 5 человек. Один из них молча заплатил кондуктору 100 рублей, и тот, не задавая никаких вопросов, отсчитал 5 билетов и отдал платившему. Вопрос: как кондуктор догадался, что оплата происходит сразу за всех пятерых, при условии, что ничто не указывало на то, что все они были вместе?

Позволю оставить задачу без ответа, потому что уверен в вашей сообразительности. А как только в комментариях появится правильный ответ, сразу вынесу ссылку сюда.
UPD: Ответ найден в комментарии пользователя ogra

Условие

Надеюсь задачка, которую я вам подкинул для разогрева, успешно подействует на вашу мозговую активность. Сейчас мы, наконец-то займемся решением олимпиадной задачи. Наша сегодняшняя задача — это задача о размене монет.

Краткий перевод условия задачи

После закупки в большом универмаге Мелу досталась сдача в размере 17 центов. Он получил одну десятицентовую монету, одну пятицентовую и 2 монеты по 1 центу. Позже, в этот же день, он делал покупки в мини-маркете, где тоже получил сдачу в размере 17 центов. На этот раз он получил две монеты по 5 центов и 7 монет по 1 центу. Тогда Мел задался вопросом: «Как много магазинов я могу посетить и получить сдачу в 17 центов различным набором монет?» После небольшого мозгового штурма, он определил, что ответ 6. Тогда он бросил вызов вам для решения более общего случая.

Напишите программу, которая определит количество различных комбинаций американских монет(1 цент, 5 центов, 10 центов, 25 и 50 центов), которые могут сложиться в определенную сумму.

Входные данные: ввод будет состоять из множества чисел между 0 и 30000 включительно, по одному в каждой строке.

Выходные данные: на каждое входное число, нужно определить число комбинаций и вывести, как показано в примере.

Output:
There are 6 ways to produce 17 cents change.
There are 4 ways to produce 11 cents change.
There is only 1 way to produce 4 cents change.

Как обычно, рекомендую вам самим попытаться решить задачу. А как только решите, возвращайтесь к нам и хвастайтесь своим результатом.

Решение

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

Можно сразу заметить, что число комбинаций не отличается при сдаче от 1 цента до 4 — это 1 вариант, при сдаче от 5 центов до 9 — это 2 варианта, при сдаче от 10 центов до 14 — это 4 варианта и т.д. Это происходит потому, что внутри такой «пятерки» монеты достоинством в 1 цент невозможно ничем заменить. Таким образом мы определили, что решать задачу для каждого числа бессмысленно, поэтому мы будем решать ее для каждой «пятерки».

Также можно заметить, комбинации для каждой следующей «пятерки» точно повторяют комбинации предыдущей «пятерки» (с добавлением в конец комбинации нужного числа монет по 1 центу) и некоторого числа новых комбинаций. Становится понятным, что число комбинаций следующей «пятерки» имеет зависимость от числа комбинаций предыдущих «пятерок». Нарисуем таблицу, где столбцами будут «пятерки», а строками виды монет, а на пресечении будет определяться, какое количество новых комбинаций породил данных вид монет ( в комбинации со всеми более мелкими) на конкретном шаге — «пятерке»:

1	5	10	15	20	25	30	35	40	45	50	55
1	1	0	0	0	0	0	0	0	0	0	0	0
5	0	1	1	1	1	1	1	1	1	1	1	1
10	0	0	1	1	2	2	3	3	4	4	5	5
25	0	0	0	0	0	1	1	2	2	3	4	5
50	0	0	0	0	0	0	0	0	0	0	1	1
∑	1	2	4	6	9	13	18	24	31	39	50	62

В последней строке выведено число комбинаций на данной «пятерке»
К примеру: на шаге 35 (8 пятерка: 35-39)
имея только 1 центовую монету, новых комбинаций не появляется,
из монет 1 цент и 5 центов, можно выдумать 1 новую комбинацию: 5+5+5+5+5+5+5+1(от 0 до 4)
1 цент, 5 центов, 10 центов — 3 комбинации: 10+10+10+5+1(от 0 до 4), 10+10+5+5+5+1, 10+5*5+1
1, 5, 10, 25 — 2 новых комбинации: 25+10+1, 25+5+5+1

Число новых комбинаций на каждом шаге из монет 1 цент и 5 центов равняется 1, потому что это комбинация порождается добавлением 5 центовой монеты к предыдущей комбинации. Т.е. для второй пятерки 5+1, потом 5+5+1, потом 5+5+5+1 и т.д., по 1 новой комбинации на каждом шаге.
Также в этой таблице не трудно углядеть рекурсивную зависимость: число новых комбинаций на шаге i, составленных из монет 1-10 равняется числу новых комбинаций из монет 1-5 на шаге i-1 плюс число новых комбинаций из монет 1-10 на шаге i-2 (когда у нас в распоряжении было на 1 десятицентовую монету меньше). Аналогично для 25-ти центовой монеты и 50-ти центовой монеты.

В итоге мы имеем 2 формулы и 3 рекурсивных зависимости:
N(1, i) = 0, кроме N(1, 0) = 1
N(5, i) = 1
N(10, i) = N(5, i-1) + N(10, i-2)
N(25, i) = N(10, i-3) + N(25, i-5)
N(50, i) = N(25, i-5) + N(50, i-10)
S(i) = S(i-1) + N(1, i) + N(5, i) + N(10, i) + N(25, i) + N(50, i)
Где N — это матрица, определенная выше, а S — искомое число комбинаций.

Теперь нам остается лишь просчитать нужное число шагов от начала до запрашиваемой «пятерки», подсчитывая на каждом шаге общее число комбинаций (S). Учитывая тот факт, что тестов в задаче будет много, можно использовать для новых тестов, ранее просчитанный кусок матрицы и дополнять лишь ее недостающую часть. Еще очень важно понимать, что при максимальной сумме, заданной условием задачи: 30000 центов, суммарное число комбинаций перевалит за пределы int и даже long, поэтому для подсчета числа комбинаций рекомендую использовать 8 байтовые беззнаковые переменные.

Полагаю, что есть более изящное решение, чем предложенное выше, но я его пока не вижу, поэтому жду от вас интересных алгоритмов. Мое решение на C++ можно скачать тут. Проверить правильность своего решения можно здесь (требуется регистрация). Удачи, господа!

• спортивное программирование
• олимпиадное программирование
• динамическое программирование

Динамическое программирование¶

В информатике многие программы пишутся для того, чтобы оптимизировать некоторую величину. Например, найти кратчайший путь между двумя точками; найти линию, лучше всего соответствующую набору точек; найти наименьшее множество объектов, удовлетворяющих некоему критерию. Для их решения существует немало стратегий, которыми пользуются учёные-информатики. Одна из целей этой книги и состоит в том, чтобы представить вам несколько различных способов поиска решения задач. Один из них — динамическое программирование, которое используют при решении такого типа задач по оптимизации.

Классическим примером задачи на оптимизацию является выдача сдачи с использованием наименьшего количества монет. Допустим, вы программист на производстве торговых автоматов. Ваша компания хочет оптимизировать усилия, выдавая как можно меньше монет на сдачу. Предположим, клиент вносит долларовую банкноту и покупает товар за 37 центов. Какое наименьшее количество монет вы можете использовать, чтобы выдать ему сдачу? Ответ: шесть — два четвертака, один десятицентовик и три пенни. Как мы получили ответ в шесть монет? Мы начали с монеты наибольшего номинала в нашем арсенале (четвертак) и использовали их столько, сколько это было возможно. Затем тоже самое проделали со следующейю по номиналу монетой, и так далее. Этот подход называется жадным методом, поскольку пытается решить настолько большой кусок задачи, насколько это возможно здесь и сейчас.

Жадный метод хорошо срабатывает, когда мы используем монеты США, но предположим, что ваша компания решила поставлять свои автоматы в Нижнюю Эльбонию, где в дополнение к монетам номиналом 1, 5, 10 и 25 центов используются монеты в 21 цент. В этом случае жадный метод потерпит поражение в поиске оптимального решения для поиска 63 центов на сдачу. С добавленной 21-центовой монетой он по-прежнему найдёт решение в шесть монет. Однако, правильным ответом будут три монеты по 21-му центу.

Давайте рассмотрим метод, о котором с уверенностью можно сказать, что он всегда найдёт оптимальное решение. Поскольку эта глава о рекурсии, вы можете догаться, что он будет рекурсивным. Начнём с определения базового случая: если мы попытаемся выдать на сдачу некоторую сумму, являющуюся одним из имеющихся номиналов, то ответ прост — одна монета.

Если это невозможно, то у нас есть несколько вариантов. Нам нужен минимум из пенни плюс количество монет, требуемых для первоначальной суммы сдачи минус пенни, или из пятицентовика плюс количество монет для первоначальной суммы сдачи минус пять центов, или из десятицентовика плюс количество монет сдачи с оригинальной суммы минус десять центов, и так далее. Таким образом, необходимое для сдачи количество монет может быть посчитано следующим образом:

\[\begin numCoins = min \begin 1 + numCoins(original amount — 1) \\ 1 + numCoins(original amount — 5) \\ 1 + numCoins(original amount — 10) \\ 1 + numCoins(original amount — 25) \end \label\end\]

Алгоритм, выполняющий то, что мы только что описали, показан в листинге 7. В строке 3 мы проверяем наш базовый случай, т.е. пытаемся дать сдачу одной монетой. Если это не получается, то делаем рекурсивный вызов для каждого номинала, меньшего, чем сумма сдачи. Строка 6 показывает, как отфильтровать список монет, которые меньше текущего значения сдачи, используя генераторы списков. Рекурсивный вызов также уменьшает общую сумму сдачи, которую мы пытаемся выдать, на номинал выбранной монеты. Это происходит в строке 7. Обратите внимание, что там же мы добавляем единицу к количеству монет на счёте, отражая факт использования монеты. Просто добавить 1 — это то же самое, что сделать рекурсивный вызов, спрашивающий, не соответствуем ли мы сейчас базовому случаю.

Листинг 7

1 2 3 4 5 6 7 8 9 10 11 12

def recMC(coinValueList,change): minCoins = change if change in coinValueList: return 1 else: for i in [c for c in coinValueList if c  change]: numCoins = 1 + recMC(coinValueList,change-i) if numCoins  minCoins: minCoins = numCoins return minCoins print(recMC([1,5,10,25],63)) 

Проблема алгоритма из листинга 7 в том, что он ужасно неэффективный. По факту, для поиска оптимального решения в четыре монеты для 63-х центовой задачи потребуется 67 716 925 рекурсивных вызовов! Чтобы понять фатальный недостаток нашего подхода, посмотрите на рисунок 5, который иллюстрирует небольшую часть 377 вызовов функции, необходимых для поиска оптимального набора монет на сдачу 26-и центов.

Каждый узел графа связан с вызовом recMC . Метка узла показывает сумму сдачи, для которой считается количество монет. Метка стрелки показывает монету, которую мы только что использовали. Следуя графу, мы можем видеть комбинации монет, имеющиеся в любой его точке. Главная проблема в том, что слишком много вычислений делается повторно. Например, граф показывает, что алгоритм будет перевычислять оптимальное количество монет, составляющих сдачу в 15 центов, как минимум трижды. Каждое такое вычисление потребует 52 вызова функции. Очевидно, что мы потратим в пустую много времени и усилий, перевычисляя уже имеющиеся результаты.

Рисунок 3: Дерево вызовов для листинга 7.

Ключ к сокращению объёма работы — это запоминать предыдущие результаты, чтобы избежать перевычисления уже известного. Простым решением будет сохранять результаты с минимальным количеством монет в таблицу. Тогда перед тем, как вычислять новый минимум, мы сначала проверим, не известен ли нам результат заранее. Если он есть в таблице — используем это значение. ActiveCode 3 демонстрирует изменённый алгоритм совместно со схемой поиска в таблице.

Run Save Load Show in Codelens

Рекурсивный подсчёт монет с поиском в таблице (lst_change2)

Обратите внимание, что в строке 6 мы добавили проверку, не содержится ли в таблице минимальное количество монет для данной суммы сдачи. Если нет, то рекурсивно вычисляем минимум и сохраняем его в таблицу. В этом изменённом алгоритме количество рекурсивных вызовов для 63-х центовой задачи уменьшилось до 221!

Хотя алгоритм из AcitveCode 3 верен, он выглядит несколько рваным. Также если мы посмотрим на список knownResults , то увидим, что в таблице есть несколько дыр. На самом деле сделанное нами описывается не термином “динамическое программирование”. Мы улучшили производительность нашей программы с помощью метода, известного как “запоминание” (чаще его называют “кэширование”).

Настоящий алгоритм динамического программирования потребует более систематичного подхода к задаче. Наше решение начинает со сдачи в один цент и систематично работает над получением требуемой суммы. Это гарантирует нам, что на каждом шаге алгоритма мы уже знаем минимальное количество монет, требуемое для сдачи любой меньшей суммы.

Давайте посмотрим, как мы можем заполнить таблицу минимумами монет для сдачи в 11 центов. Рисунок 4 иллюстрирует этот процесс. Мы начинаем с одного цента. Единственное возможное решение — одна монета (пенни). Следующая строка показывает минимум для одного и двух центов. Решение вновь единственное и равняется двум пенни. На пятой строке жизнь становится интереснее. Теперь у нас есть два варианта для рассмотрения: пять пенни или один пятицентовик. Как мы решим, какой из них лучше? Мы проконсультируемся с таблицей и увидим, что сдача в четыре цента даст четыре монеты, плюс ещё одно пенни — итого пять монет. Или мы рассмотрим нуль монет плюс один пятицентовик, что даст нам одну монету. Поскольку минимум из одного и пяти равен одному, то мы сохраняем в таблице единицу. Перенесёмся в конец таблицы и рассмотрим 11 центов. Рисунок 5 показывает три варианта для изучения:

1. Пенни плюс минимальное количество монет для сдачи в 11 — 1 = 10 центов (1)
2. Пятицентовик плюс минимально количество монет для сдачи в 11 — 5 = 6 центов (2)
3. Десятицентовик плюс минимальное количество монет для сдачи в 11 — 10 = 1 цент (1)

Варианты 1 и 3 дают нам ответ в две монеты, что и является минимальным количеством для сдачи в 11 центов.

Рисунок 4: Минимальное количество монет, составляющее сдачу.

Рисунок 5: Три варианта для нахождения минимального количества монет для сдачи в 11 центов.

Листинг 8 — это алгоритм динамического программирования, решающий нашу задачу о сдаче. dpMakeChange принимает три параметра: список действующих номиналов монет, сумму сдачи, которую мы хотим выдать, и список из минимальных количеств монет, необходимых для выдачи каждого значения. Когда функция закончит свою работу, minCoins будет содержать решение для всех значений от нуля до change .

Листинг 8

def dpMakeChange(coinValueList,change,minCoins): for cents in range(change+1): coinCount = cents for j in [c for c in coinValueList if c  cents]: if minCoins[cents-j] + 1  coinCount: coinCount = minCoins[cents-j]+1 minCoins[cents] = coinCount return minCoins[change] 

Обратите внимание, что dpMakeChange не является рекурсивной, хотя начинали мы с рекурсивного решения задачи. Важно понимать: одна возможность написать рекурсивное решение не означает, что оно будет лучшим или наиболее эффективным. Основная часть работы в этой функции приходится на цикл, который начинается в строке 4. В нём мы рассматриваем все возможные сочетания монет, дающие заданную сумму, определённую cents . Как мы уже делали в примере для одиннадцати центов выше, мы запоминаем минимальные значения и сохраняем их в списке minCoins .

Хотя этот алгоритм выдачи сдачи проделывает хорошую работу по представлению минимального количества монет, он не поможет нам выдать сдачу пока мы не отследим монеты, которые используем. Для этого можно легко расширить dpMakeChange , используя простое запоминание последней добавленной монеты для каждого экземпляра в таблице minCoins . Если мы знаем последнюю добавленную монету, её значение можно просто вычесть, чтобы найти в таблице предыдущий экземпляр, который скажет нам последнюю добавленную монету для составления этой суммы. Мы сможем отслеживат монеты по таблице до тех пор, пока не придём к началу.

ActiveCode 4 демонстрирует алгоритм dpMakeChange , изменённый для возможности отслеживать использованные монеты, вместе с функцией printCoins , проходящей по таблице в обратном направлении и печатающей значение каждой использованной монеты. Это демонстрирует алгоритм, в действии решающий проблему наших друзей из Нижней Эльбонии. Первые две строки в main устанавливают сумму, которую нужно конвертировать, и создают список используемых монет. Следующие две строки инициализируют список, необходимый для хранения результатов. coinsUsed — список монет, использованных для выдачи сдачи, а coinCount — минимальное количество монет для сдачи суммы, связанной с позицией в списке.

Обратите внимание, что монеты, которые мы печатаем, берутся непосредственно из массива coinsUsed . На первом вызове мы начинаем с 63-го индекса в массиве и печатаем 21. Затем берём 63 — 21 = 42 и смотрим на 42-й элемент в списке, где вновь обнаруживаем сохранённое 21. Наконец, 21-й элемент списка тоже содержит 21, что даёт нам три монеты в 21 цент.

Динамическое программирование

Рассмотрим следующую задачу. В обороте находятся банкноты k различных номиналов: a₁, a₂, . a_k рублей. Банкомат должен выдать сумму в N рублей при помощи минимального количества банкнот или сообщить, что запрашиваемую сумму выдать нельзя. Будем считать, что запасы банкнот каждого номинала неограничены.

Рассмотрим такой алгоритм: будем выдавать банкноты наибольшего номинала, пока это возможно, затем переходим к следующему номиналу. Например, если имеются банкноты в 10, 50, 100, 500, 1000 рублей, то при N = 740 рублей такой алгоритм выдаст банкноты в 500, 100, 100, 10, 10, 10, 10 рублей. Подобные алгоритмы называют «жадными», поскольку каждый раз при принятии решения выбирается тот вариант, который кажется наилучшим в данной ситуации (чтобы использовать наименьшее число банкнот каждый раз выбирается наибольшая из возможных банкнот).

Но для решения данной задачи в общем случае жадный алгоритм оказывается неприменимым. Например, если есть банкноты номиналом в 10, 60 и 100 рублей, то при N = 120 жадный алгоритм выдаст три банкноты: 100 + 10 + 10, хотя есть способ, использующий две банкноты: 60 + 60. А если номиналов банкнот только два: 60 и 100 рублей, то жадный алгоритм вообще не сможет найти решения.

Но эту задачу можно решить при помощи метода динамического программирования. Пусть F(n) — минимальное количество банкнот, которым можно заплатить сумму в n рублей. Очевидно, что F(0) = 0, F(a₁) = F(a₂) =. = F(a_k) = 1. Если некоторую сумму n невозможно выдать, будем считать, что F(n) = (бесконечность).

Выведем рекуррентную формулу для F(n), считая, что значения F(0), F(1), . F(n — 1) уже вычислены. Как можно выдать сумму n? Мы можем выдать сумму n — a₁, а потом добавить одну банкноту номиналом a₁. Тогда нам понадобится F(n — a₁) + 1 банкнота. Можем выдать сумму n — a₂ и добавить одну банкноту номиналом a₂, для такого способа понадобится F(n — a₂) + 1 банкнота и т. д. Из всевозможных способов выберем наилучший, то есть:

F(n) = min(F(n — a₁), F(n — a₂). F(n — a_k)) + 1.

Теперь заведем массив F[n+1], который будем последовательно заполнять значениями выписанного рекуррентного соотношения. Будем предполагать, что количество номиналов банкнот хранится в переменной int k, а сами номиналы хранятся в массиве int a[k].

const int INF=1000000000; // Значение константы >бесконечность> 
int F[n+1]; 
F[0]=0; 
int m, i; 
for(m=1; m  < // m - сумма, которую нужно выдать 
F[m]=INF; // помечаем, что сумму m выдать нельзя 
for(i=0; i  < 
if(m>=a[i] && F[m-a[i]]+1 F[m] = F[m-a[i]]+1; // изменяем значение F[m], если нашли 
> // лучший способ выдать сумму m 
>

После окончания этого алгоритма в элементе F[n] будет храниться минимальное количество банкнот, необходимых, чтобы выдать сумму n. Как теперь вывести представление суммы n при помощи F(n) банкнот? Опять рассмотрим все номиналы банкнот и значения n — a₁, n — a₂, . n — a_k. Если для какого-то i окажется, что F(n — a_i) = F(n) — 1, значит, мы можем выдать банкноту в a_i рублей и после этого свести задачу к выдаче суммы n — a_i, и так будем продолжать этот процесс, пока величина выдаваемой суммы не станет равна 0:

if (F[n]==INF) 
coutelse 
while(n>0) 
for(i=0;i if (F[n-a[i]]==F[n]-1) 
 cout n-=a[i]; 
break; 
>