задачка

[avva]

По внутренней рассылке прислали задачку. Очень может быть, что нетривиальную; решения я не знаю. Звучит красиво... думаю.

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

Есть наборы, для которых "жадный" алгоритм всегда приведет к наименьшему возможному количеству монет (скажем, набор из 10, 5, 3 и 1 - такой). А есть наборы, для которых иногда можно воспользоваться меньшим количеством монет, чем дает "жадный" алгоритм (например, набор достоинств в 25, 20, 10, 5 и 1 такой: сумму в 40 денежных единиц можно в нем выразить двумя монетами по 20, а "жадный" алгоритм дает три монеты: 25, 10 и 5).

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

P.S. Если вы просто знаете правильное решение (а не придумали его сами), не надо им делиться пока, хочу подумать сам.

Comments

Re: совсем простой алгоритм

[knop.livejournal.com]

Я пока не понял, что такое L, но, вероятно, что да, по идее это просто обязано быть тем же самым. Поскольку там критериальное условие: если не проверить хотя бы одно из чисел моего списка, то набор монет может быть "неправильным" (и минимальная неправильность будет именно на этом непроверенном числе), а если проверить все - то никаких других проверять и не нужно.
Т.е. вам сейчас осталось только убедиться в минимальности числа делаемых проверок. Ну или в минимальности хотя бы по порядку величины. (Сорри, я возвращаюсь к тому, с чего начал: что такое L?)

циклы

[falcao.livejournal.com]

Я не определял здесь L, так как это было по сути дела продолжение предыдущих комментов из этого треда, где было сказано следующее:

> L -- максимальное достоинство монеты

То есть в итоге алгоритм выглядит следующим образом. Полагаем a[i]=0 и рассматриваем цикл по i от 1 до 2L-1. Для данного i рассматриваем монету максимального достоинства k не превосходящего i, полагая затем a[i]=1+a[i-k]. После прохождения цикла в a[i] хранится число шагов "жадного" алгоритма, нужное для того, чтобы набрать сумму i.

Теперь проходим цикл по i заново, где при каждом i первое слагаемое варьируем, то есть внутри цикла возникает ещё один. Переменная j нового цикла пробегает все возможные достоинства монет, меньшие i. При этом смотрим на величину 1+a[i-j] и проверяем, не будет ли она при каком-то j меньше нежели a[i].

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

Что касается минимальности числа проверок, то я над этим пока не думал. Я пока не знаю, совпадает ли описанное с тем, что Вы предлагаете.

Re: циклы

[knop.livejournal.com]

Нет, тогда алгоритмы точно разные.
Фишка в том, что в известном мне решении сложность алгоритма пропорциональна квадрату ЧИСЛА монет, а не квадрату ДОСТОИНСТВА наибольшей монеты. Т.е. максимальная монета может быть хоть 314159265358979 рублей, но если она пятая, то алгоритм проверки закончится очень быстро...

деление с остатком

[falcao.livejournal.com]

Я думаю, что в моём случае, конечно, всё тоже сводится к числу монет, потому что составлять такой длинный массив на самом деле не нужно. Чтобы вычислить a[i], достаточно поделить i на k остатком (в обозначениях, приводимых выше). Если i=kq+r, то полагаем a[i]=q+a[r], то есть можно использовать рекурсивную процедуру-функцию, которая по скорости примерно такая же как алгоритм Евклида.

Я всё это дело рассматривал только "теоретически", но сейчас стало ясно, что практический алгоритм там совсем не сложный. Я попробую сегодня ближе к ночи написать коротенькую программу для Maple.

Re: циклы

[myckolah.livejournal.com]

монеты 1,16,40; проверяем 48 (http://avva.livejournal.com/1782821.html?thread=43390757#t43390757). если варьировать только первое слагаемое, насколько я понял, верного результата вы не получите.

всё верно

[falcao.livejournal.com]

Всё получается как раз. ЖА даёт 48=40+1+...+1 с 9 монетами. Теперь заменяем первое слагаемое на 16 вместо 40. К оставшемуся числу 32 применяем ЖА, и в итоге имеем 48=16+16+16 с тремя монетами.

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