задачка

[avva]

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

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

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

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

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

Comments

2L вместо L^2

[falcao.livejournal.com]

Ваше решение, конечно, короче. Я просто представил себе готовую конструкцию из теории кодирования и понял, что она здесь тоже работает. Оценка получается X^2; у Вас, как я понимаю, она равна Y*X^2/(X-Y), то есть тоже высокая.

Моё решение, простите за невольный каламбур, было в некотором роде "выстрелом из пушки по воробьям" :) Оно в какой-то мере напоминает "сведение к уже решённой задаче" из хохмочки про выливание воды из чайника. На самом деле оценку там легко снизить до 2L.

Левая арка сверху имеет длину не более L, левая нижняя -- короче. И далее как сверху, так и снизу применяется "жадный" алгоритм. Если число N не меньше 2L, то в обоих случаях следующее слагаемое будет равно L. Тогда на него можно сократить, переходя к числу N-L.

В таком виде перебор получается уже весьма скромным.

Я не думаю, что существует какое-то легко выписываемое условие на числа, потому что устройство арок в реализуемых примерах может быть довольно сложным. В любом случае, придётся перебирать пары длин начальных арок как минимум. В продолжении процесса тоже возникают разветвления, и вообще-то получается некоторый процесс на графе, вершинами которого будут числа, а направленные рёбра соответствуют разложениям исходных чисел, равных достоинствам монет. Если монета M равна k'+k_1+...+k_s+k'', где k_1,...,k_s равны достоинствам некоторых монет, то числа k' и k'' соединяем дугой с "меткой" (k_1,...,k_s). Достаточно вообще-то запоминать только s и сумму этих слагаемых. Случай k'=k''=0, s=1 мы не принимаем в расчёт.

Изучая направленные циклы на этом графе из 0 в 0, можно как-то отследить все нужные случаи, учитывая "жадность" алгоритмов. Здесь я тоже взял обычный для такой ситуации граф из теории кодирования.

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

[falcao.livejournal.com]

Тот граф, который я здесь предлагаю рассматривать, отличается от Вашего. Он у меня такой, который возникает в алгоритме проверки кодирования на однозначность. Я, впрочем, не уверен, что столь усложнённый вариант требуется.

Вообще-то из той оценки, которую я дал выше, вытекает довольно несложный алгоритм, сложность которого нетрудно оценить. А именно, перебираются числа менее 2L. Для каждого из них последовательно применяется сначала "жадный" алгоритм и подсчитывается число монет. Результаты заносятся в массив. Затем первое слагаемое уменьшаем, и к оставшейся части применяем "жадный" алгоритм, значение которого на самом деле к этому моменту известно. То есть граф тут даже и не нужен.

Возможно, что это совпадает или почти совпадает с тем, о чём ниже написал knop.

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

[occuserpens.livejournal.com]

wow!

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 не подошло, то есть не дало бы уменьшения числа монет, то взяли бы следующее значение. При этом те суммы, в которых попадается хотя бы одно слагаемое из "жадного" набора, можно для убыстрения браковать.