82
правки
Изменения
Нет описания правки
== Задача о банкомате. ==
В вариации задаче о банкомате, которую мы рассмотрим, у вас имеется <tex>N</tex> монет. Каждая монета характеризуется двумя параметрами: номиналом и весом. При этом все номиналы являются степенями двойки и не превышают <tex>2^0</tex>. Необходимо выбрать из имеющихся монет некоторый набор так, чтобы их суммарный номинал был равен <tex>S</tex> (натуральное число), а суммарный вес минимален.
== Алгоритм решения задачи о банкомате. ==
Рассмотрим алгоритм решения приведенной выше вариации задачи о банкомате.
# Разделим имеющиеся у нас монеты на списки по номиналу (свой список для каждого номинала) и упорядочим монеты по возрастанию весов внутри списков.
