![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaПо внутренней рассылке прислали задачку. Очень может быть, что нетривиальную; решения я не знаю. Звучит красиво... думаю.
Пусть у нас есть какой-то набор достоинств монет, так, что любую сумму можно собрать из монет данного набора (количество индивидуальных монет каждого достоинства неограничено). Для любой суммы, чтобы собрать ее посредством данного набора, можно воспользоваться "жадным" алгоритмом: каждый раз брать наибольшую возможную монету, меньшую оставшейся суммы, вычитать ее, и продолжать так, пока ничего не останется.
Есть наборы, для которых "жадный" алгоритм всегда приведет к наименьшему возможному количеству монет (скажем, набор из 10, 5, 3 и 1 - такой). А есть наборы, для которых иногда можно воспользоваться меньшим количеством монет, чем дает "жадный" алгоритм (например, набор достоинств в 25, 20, 10, 5 и 1 такой: сумму в 40 денежных единиц можно в нем выразить двумя монетами по 20, а "жадный" алгоритм дает три монеты: 25, 10 и 5).
Вопрос: как для любого набора определить, к какой из этих двух групп он относится, т.е. всегда ли жадный алгоритм дает для него наименьшее количество монет?
P.S. Если вы просто знаете правильное решение (а не придумали его сами), не надо им делиться пока, хочу подумать сам.
Пусть у нас есть какой-то набор достоинств монет, так, что любую сумму можно собрать из монет данного набора (количество индивидуальных монет каждого достоинства неограничено). Для любой суммы, чтобы собрать ее посредством данного набора, можно воспользоваться "жадным" алгоритмом: каждый раз брать наибольшую возможную монету, меньшую оставшейся суммы, вычитать ее, и продолжать так, пока ничего не останется.
Есть наборы, для которых "жадный" алгоритм всегда приведет к наименьшему возможному количеству монет (скажем, набор из 10, 5, 3 и 1 - такой). А есть наборы, для которых иногда можно воспользоваться меньшим количеством монет, чем дает "жадный" алгоритм (например, набор достоинств в 25, 20, 10, 5 и 1 такой: сумму в 40 денежных единиц можно в нем выразить двумя монетами по 20, а "жадный" алгоритм дает три монеты: 25, 10 и 5).
Вопрос: как для любого набора определить, к какой из этих двух групп он относится, т.е. всегда ли жадный алгоритм дает для него наименьшее количество монет?
P.S. Если вы просто знаете правильное решение (а не придумали его сами), не надо им делиться пока, хочу подумать сам.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2007-07-08 12:47 am (UTC)Вроде бы то, что я знаю, вообще не требует перебора.
Там рассматриваются примерно C_n^2 конкретных чисел, для каждого из которых сравниваются две величины - длина жадного представления и длина еще одного конкретного представления. Если для каждого из этих чисел жадное разложение _не длиннее альтернативного_, то жадный алгоритм будет давать кратчайшее представление для любой суммы.
Обратная теорема тоже верна.
no subject
Date: 2007-07-08 12:53 am (UTC)