задачка

[avva]

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

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

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

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

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

Comments

[yanis.livejournal.com]

наверное если в наборе соседние достоинства не кратные то жадный алгоритм не всегда лучший

[avva.livejournal.com]

10,5,3,1 кажется всегда выигрывает в жадном, но не все соседние кратные.

[sergeax.livejournal.com]

А не достаточно ли того, чтобы достоинство каждой следующей по возрастанию номинала монеты было больше или равно удвоенному достоинству предыдущей?

[max-i-m.livejournal.com]

Net. 1,16,40. Probuem 48.

[mgar.livejournal.com]

Кажется, каждая следующая монетка должна быть не просто больше, но и кратна предыдущей => кратна всем предыдущим. Тогда ее нельзя будет обойти.

Это, пожалуй, достаточное условие. Но необходимое ли?

[max-i-m.livejournal.com]

>что любую сумму можно собрать из монет данного набора

то есть в наборе есть 1?

или предполагалось "любую сумму свыше определенной можно собрать из монет данного набора" (то есть НОК набора равен 1).

Не уверен, что это влияет на решение, но все же.

[max-i-m.livejournal.com]

Hm.
Вариант "любую сумму свыше определенной" не подходит - это условие можно было бы опустить не меняя существенно задачи.

[avva.livejournal.com]

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

[muchacho.livejournal.com]

Блин, хотел лечь полчаса назад.

[occuserpens.livejournal.com]

Сдается мне, что в общем виде, для любого набора монет, это очень "нечестная" задача, т.е. за ней стоит серьезный результат. Если не прав, смело бейте меня ногами.

[knop.livejournal.com]

Я не очень знаю, что такое "нечестная" задача.
Результат, который я в ней знаю - да, вполне приличный.
Но, между прочем, получен он был школьником 10-го класса

[relf.livejournal.com]

Эту задачу мы когда-то решали в fido7.ru.math:
http://groups.google.com/group/fido7.ru.math/browse_thread/thread/9d99e936feed0e4b/
К сожалению, сейчас на Google Groups глюки с кодировками, а где еще можно посмотреть в интернете я не знаю.
Но могу выслать этот тред на емайл, если кому-то интересно.

[max-i-m.livejournal.com]

Вышлите, пожалуйста. max_i_m@mail.ru

оценка

[falcao.livejournal.com]

Здесь, похоже, проходит тот же трюк, что и при обосновании алгоритма проверки алфавитного кодирования на однозначность (то есть проверки гомоморфизма свободных полугрупп на инъективность).

Пусть задан конечный набор монет целочисленного достоинства, где L -- максимальное достоинство монеты (то же самое, видимо, проходит и для нецелочисленных наборов). Предположим, что "жадный" алгоритм в общем случае не приводит к минимальному числу монет, и пусть N -- наименьшее число, для которого "жадный" алгоритм даёт не оптимальный ответ. Достаточно установить справедливость оценки N <= L^2, после чего всё сводится к конечному перебору. (Практически перебор становится меньше, если построить некоторый вспомогательный граф, но я этого описывать не буду.)

Далее действуем так. Для представления числа K в виде суммы слагаемых k_1+...+k_s можно нарисовать "арки", то есть взять отрезок длиной K, разбить его на части с длинами k_1,...,k_s, соответственно, а затем соединить точки деления дугами в верхней или нижней полуплоскости. На таком языке далее удобно будет вести описание.

У нас имеется два представления числа N в виде суммы невозрастающих слагаемых, причём первое соответствует "жадному" алгоритму. Нарисуем соответствующие арки сверху отрезка длиной N, а для второго представления с меньшим числом слагаемых нарисуем арки снизу (их длины также не возрастают).

Из условия выбора числа N ясно, что у верхних арок нет общих внутренних точке с нижними. Первая слева арка верхнего разложения строго длиннее первой слева нижней. Кроме того, без ограничения общности можно считать, что все нижние арки кроме первой формируют разложение получающегося при этом числа по "жадному" алгоритму.

Разобьём отрезок длиной N на кусочки, отмечая на нём концы всех используемых арок. Кусочек может а) сопадать с одной из арок (верхней или нижней), б) быть началом верхней арки и концом нижней, в) быть концом верхней арки и началом нижней -- начала и концы здесь полагаются собственными.

Докажем, что кусочки типа б) имеют попарно различные длины. Аналогично для кусочков типа в).

Предположим, что есть два кусочка типа б) длиной u. (Тут удобно сделать рисунок для наглядности.) Тогда имеем N=N1+u+N2+u+N3, где в верхнем разбиении N1, u+N2, u+N3 будут полностью состоять из арок, а в нижнем то же верно относительно N1+u, N2+u, N3.

Рассмотрим число N'=N1+u+N3, представляя его двумя способами в виде слагаемых: N1+(u+N3) для верха, с заведомо "жадным" алгоритмом и (N1+u)+N3 для низа. При этом изъятое как сверху, так и снизу количество арок равно одному и тому же числу -- количеству слагаемых, к которому приводит "жадный" алгоритм, применённый к числу u+N2=N2+u. Мы получим число, N', меньшее N, у которого вверху арок больше чем внизу, и при этом верхнее разбиение соответствует "жадному" алгоритму. Это приводит к противоречию с выбором числа N.

Легко понять, что длина отрезка типа б) или в) не превосходит L/2. (Для более грубой оценки можно было бы взять L-1.) Запишем теперь N в виде суммы N=v_0+u+1+v_1+...+u_r+v_r, где u_1,...,u_r -- все части типа б) или в). Из того, что все части типа б) попарно различны по длине, следует, что их не больше L/2. То же для частей типа в), откуда r <= L.

Положим для удобства u_0=u_{r+1}=0. Из устройства арок ясно, что u_{i}+v_{i}+u+{i+1} есть длина арки при любом i от 0 до r, а потому она не больше L. Тогда получаем, что N=(u_0+v_1+u_1)+...+(u_r+v_r+u_{r+1})-(u_1+...+u_r) <= L(r+1)-r=(L-1)r+L <= (L-1)L+L=L^2.

QED

Re: оценка

[avva.livejournal.com]

Я тоже доказал, что можно свести к перебору, кажется, несколько проще Вашего метода - если нигде не ошибся. Пусть X - наибольшее достоинство, Y следующее за ним, N - большое положительное целое число, которое предстоит зафиксировать. Любое число между NX и (N+1)X представимо жадным алгоритмом с помощью не более N+X монет. Если такое число является минимальным контрпримером, наказывающим жадность, то его оптимальное не-жадное представление не может включать в себя X, ввиду оптимальности; если в нем тоже не более N+X монет, то сумма этих монет не может быть больше (N+X)Y. Выберем N достаточно большим, чтобы это число - (N+X)Y - было меньше NX, это легко сделать; тогда никакое число между NX и (N+1)X не может быть минимальным контрпримером, и очевидно, что для еще больших значений N это сохраняется. Все числа меньше NX перебираем "вручную".

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

[knop.livejournal.com]

Ну так как - делиться информацией или подумаете пока самостоятельно?
Вроде бы то, что я знаю, вообще не требует перебора.
Там рассматриваются примерно C_n^2 конкретных чисел, для каждого из которых сравниваются две величины - длина жадного представления и длина еще одного конкретного представления. Если для каждого из этих чисел жадное разложение _не длиннее альтернативного_, то жадный алгоритм будет давать кратчайшее представление для любой суммы.

Обратная теорема тоже верна.

[avva.livejournal.com]

Интересно. Я пытался думать в этом направлении, но ничего хорошего не додумал. Если Вам не очень трудно, напишите Ваше решение завтра где-то в то же время? Чтобы у тех, кто хочет сам, было время подумать, включая и меня - а я как раз буду в самолете к тому времени, и над Атлантическим океаном смогу еще немного помедитировать, если до тех пор не придумаю ничего.

[bugabuga.livejournal.com]

Для наборов вида N1 N2 N3 ... 1, из которых можно представить любую сумму, достаточным условием неоптимальности жадного алгоритма будет:
Разница номиналов любой пары последующих монет (N1 < N2) меньше чем N2*2 :)
В таких случаях нежадный алгоритм может построить сумму N2*2 взяв две монетки N2. А жадный алгоритм всегда будет использовать N1 + a*N3 + b*N4 .... что будет 3 или более монет.

Осталось понять как написать математическое доказательство. Тупею от года в год :(

[bugabuga.livejournal.com]

p.s. ах да, и N1 + N3 != N2 :) но если даже равно то будет просто равный результат для жадного и нежадного

[knop.livejournal.com]

но существуют и такие наборы, для которых оно не выполнено, а жадный алгоритм тем не менее не оптимален

[averros.livejournal.com]

http://www.perlmonks.org/?node_id=438118

а вот и теория, ага.

[averros.livejournal.com]

http://citeseer.ist.psu.edu/cache/papers/cs/4785/http:zSzzSzsimon.cs.cornell.eduzSzInfozSzPeoplezSzpearsonzSzchange.pdf/pearson94polynomialtime.pdf

[ivan-gandhi.livejournal.com]

Ну тут прямо филиал misc.

Кстати, пославший задачу - автор сайта advogato.org.

[sply.livejournal.com]

Принадлежность к группе оптимального жадного - каждый K(i) должен быть >= S(i-1) и <= 2*S(i-1), где S(n) = сумма K(0)..K(n)

Нутром чую, доказать не могу, тесты подтверждают.

[sply.livejournal.com]

и оптимальная середина, которая даст наименьшие наборы для всех исел - ряд k(i) = 2^i.

Обещанный ТеХ 1993 года

[knop.livejournal.com]

Сейчас выправил (и то не все) только какие-то ТеХовские мелочи, чтобы компилировалось нормально. По существу правок не вносил.
В архиве - TeX-файл и на всякий случай pdf-ка, сделанная из dvi.
Объем - ок. 260 Кб.
http://www.chgk.info/~knop/articles/p93money.zip

[aburachil.livejournal.com]

Я чего-то не понимаю, или условие "любую сумму можно собрать из монет данного набора" эквивалентно условию "в данном наборе есть монета достоинством 1 тугрик"?

[avva.livejournal.com]

да