Задача о размене монет

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

Если глобальная оптимальность алгоритма имеет место практически всегда, его обычно предпочитают другим методам оптимизации, таким как динамическое программирование.

Содержание

Условия применимости [ править | править код ]

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

Принцип жадного выбора [ править | править код ]

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

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

Оптимальность для подзадач [ править | править код ]

Говорят, что задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит в себе оптимальные решения для всех её подзадач. Например, в задаче о выборе заявок можно заметить, что если A <displaystyle A> — оптимальный набор заявок, содержащий заявку номер 1, то A ′ = A ∖ < 1 ><displaystyle A^<prime >=Asetminus left<1
ight>> — оптимальный набор заявок для меньшего множества заявок S ′ <displaystyle S^<prime >> , состоящего из тех заявок, для которых s i ≤ f 1 <displaystyle s_leq f_<1>> .

Читайте также:  Dcb association y389ok42qa66f478t94a9cj8l5trlt7lk что значит эта смс

Примеры [ править | править код ]

Размен монет [ править | править код ]

Задача. Монетная система некоторого государства состоит из монет достоинством a 1 = 1 a 2 . . . a n <displaystyle a_<1>=1 . Требуется выдать сумму S <displaystyle S> наименьшим возможным количеством монет.

Жадный алгоритм решения этой задачи таков. Берётся наибольшее возможное количество монет достоинства a n <displaystyle a_> : x n = ⌊ S / a n ⌋ <displaystyle x_=lfloor S/a_
floor > . Таким же образом получаем, сколько нужно монет меньшего номинала, и т. д.

Для данной задачи жадный алгоритм не всегда даёт оптимальное решение, а только для некоторых, называемых каноническими, монетных систем, вроде используемых в США (1, 5, 10, 25 центов). Неканонические системы таким свойством не обладают. Так, например, сумму в 24 копейки монетами в 1, 5 и 7 коп. жадный алгоритм разменивает так: 7 коп. — 3 шт., 1 коп. — 3 шт., в то время как правильное решение — 7 коп. — 2 шт., 5 коп. — 2 шт. [1]

Выбор заявок [ править | править код ]

Формулировка № 1. Даны n <displaystyle n> заявок на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия ( s i <displaystyle s_> и f i <displaystyle f_> для i <displaystyle i> -й заявки). В случае пересечения заявок можно удовлетворить лишь одну из них. Заявки с номерами i <displaystyle i> и j <displaystyle j> совместны, если интервалы [ s i , f i ) <displaystyle [s_,f_)> и [ s j , f j ) <displaystyle [s_,f_)> не пересекаются (то есть f i ≤ s j <displaystyle f_leq s_> или f j ≤ s i <displaystyle f_leq s_> ). Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.

Формулировка № 2. На конференции, чтобы отвести больше времени на неформальное общение, различные секции разнесли по разным аудиториям. Учёный с чрезвычайно широкими интересами хочет посетить несколько докладов, проходящих в разных секциях. Известно начало s i <displaystyle s_> и конец f i <displaystyle f_> каждого доклада. Определить, какое максимальное количество докладов можно посетить.

Читайте также:  Php входит ли подстрока в строку

Приведём жадный алгоритм, решающий данную задачу. При этом полагаем, что заявки упорядочены в порядке возрастания времени окончания. Если это не так, то можно отсортировать их за время O ( n log ⁡ n ) <displaystyle O(nlog n)> ; заявки с одинаковым временем конца располагаем в произвольном порядке.

На вход данному алгоритму подаются массивы начала и окончания занятий. Множество A состоит из номеров выбранных заявок, а j — номер последней заявки. Жадный алгоритм ищет заявку, начинающуюся не ранее окончания j-той, затем найденную заявку включает в A, а j присваивает её номер. Таким образом, каждый раз мы выбираем то (ещё не начавшееся) занятие, до конца которого осталось меньше всего времени.

Алгоритм работает за O ( n log ⁡ n + n ) <displaystyle O(nlog n+n)> , то есть сортировка плюс выборка. На каждом шаге выбирается наилучшее решение. Покажем, что в итоге получится оптимум.

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

Другие жадные алгоритмы [ править | править код ]

  • Алгоритм Хаффмана (адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью).
  • Алгоритм Крускала (поиск остовного дерева минимального веса в графе).
  • Алгоритм Прима (поиск остовного дерева минимального веса в связном графе).

Обобщением жадных алгоритмов является алгоритм Радо — Эдмондса.

Задачи, в которых жадные алгоритмы не дают оптимального решения [ править | править код ]

Для ряда задач, относящихся к классу NP, жадные алгоритмы не дают оптимального решения. К ним относятся:

Тем не менее, в ряде задач жадные алгоритмы дают неплохие приближённые решения.

Читайте также:  Как переводить комментарии в ютубе

Решаю задачу о размене монет. Условие приведено ниже. Проблема в том, что все решения, которые я испытал занимают много памяти. И не применимы для больших входных данных например, для 1 000 000 000 . Вопрос в том как можно оптимизировать решения для больших чисел? Или может есть какая-нибудь более эффективная идея для решения этой задачи?

Условие задачи:

По данным числам 1≤n≤30 и 1≤w≤10^9 и набору чисел 1≤v[1],…,v[n]≤10^9 найдите минимальное число k , для которого число w можно представить как сумму k чисел из набора . Каждое число из набора можно использовать сколько угодно раз. Известно, что в наборе есть единица и что для любой пары чисел из набора одно из них делится на другое. Гарантируется, что в оптимальном ответе число слагаемых не превосходит 10^4 .

Выведите число k и сами слагаемые.

Решение на C++:

Решение на Python. Вариант 1:

Решение на Python. Вариант 2:

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

среда, 20 апреля 2011 г.

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

Сколькими способами можно разменять сумму в 1 доллар, если имеются монеты по 50, 25, 10, 5 и 1 цент?

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

Оцените статью
Добавить комментарий