?

Log in

No account? Create an account
задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка [июл. 8, 2007|01:27 am]
Anatoly Vorobey
[Tags|, ]

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

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

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

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

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

Comments:
[User Picture]From: yanis
2007-07-07 10:45 pm
наверное если в наборе соседние достоинства не кратные то жадный алгоритм не всегда лучший
(Ответить) (Thread)
[User Picture]From: avva
2007-07-08 12:01 am
10,5,3,1 кажется всегда выигрывает в жадном, но не все соседние кратные.
(Ответить) (Parent) (Thread)
[User Picture]From: sergeax
2007-07-07 11:08 pm
А не достаточно ли того, чтобы достоинство каждой следующей по возрастанию номинала монеты было больше или равно удвоенному достоинству предыдущей?
(Ответить) (Thread)
[User Picture]From: max_i_m
2007-07-07 11:14 pm
Net. 1,16,40. Probuem 48.
(Ответить) (Parent) (Thread)
[User Picture]From: max_i_m
2007-07-07 11:08 pm
>что любую сумму можно собрать из монет данного набора

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

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

Не уверен, что это влияет на решение, но все же.
(Ответить) (Thread)
[User Picture]From: max_i_m
2007-07-07 11:30 pm
Hm.
Вариант "любую сумму свыше определенной" не подходит - это условие можно было бы опустить не меняя существенно задачи.

(Ответить) (Parent) (Thread)
[User Picture]From: muchacho
2007-07-07 11:23 pm
Блин, хотел лечь полчаса назад.
(Ответить) (Thread)
[User Picture]From: occuserpens
2007-07-07 11:27 pm
Сдается мне, что в общем виде, для любого набора монет, это очень "нечестная" задача, т.е. за ней стоит серьезный результат. Если не прав, смело бейте меня ногами.
(Ответить) (Thread)
[User Picture]From: knop
2007-07-08 12:31 am
Я не очень знаю, что такое "нечестная" задача.
Результат, который я в ней знаю - да, вполне приличный.
Но, между прочем, получен он был школьником 10-го класса
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: relf
2007-07-07 11:35 pm
Эту задачу мы когда-то решали в fido7.ru.math:
http://groups.google.com/group/fido7.ru.math/browse_thread/thread/9d99e936feed0e4b/
К сожалению, сейчас на Google Groups глюки с кодировками, а где еще можно посмотреть в интернете я не знаю.
Но могу выслать этот тред на емайл, если кому-то интересно.
(Ответить) (Thread)
[User Picture]From: max_i_m
2007-07-07 11:43 pm
Вышлите, пожалуйста. max_i_m@mail.ru
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: falcao
2007-07-08 12:27 am

оценка

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

Пусть задан конечный набор монет целочисленного достоинства, где 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
(Ответить) (Thread)
[User Picture]From: avva
2007-07-08 12:44 am

Re: оценка

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

Но, наверное, это все же "нечестное" решение в том смысле, что требуется придумать что-то интересное, связанное со свойствами самих чисел, а не алгоритм, который теоретически все проверит путем долгого перебора.
(Ответить) (Parent) (Thread) (Развернуть)
(Удалённый комментарий)
[User Picture]From: knop
2007-07-08 12:47 am
Ну так как - делиться информацией или подумаете пока самостоятельно?
Вроде бы то, что я знаю, вообще не требует перебора.
Там рассматриваются примерно C_n^2 конкретных чисел, для каждого из которых сравниваются две величины - длина жадного представления и длина еще одного конкретного представления. Если для каждого из этих чисел жадное разложение _не длиннее альтернативного_, то жадный алгоритм будет давать кратчайшее представление для любой суммы.

Обратная теорема тоже верна.
(Ответить) (Thread)
[User Picture]From: avva
2007-07-08 12:53 am
Интересно. Я пытался думать в этом направлении, но ничего хорошего не додумал. Если Вам не очень трудно, напишите Ваше решение завтра где-то в то же время? Чтобы у тех, кто хочет сам, было время подумать, включая и меня - а я как раз буду в самолете к тому времени, и над Атлантическим океаном смогу еще немного помедитировать, если до тех пор не придумаю ничего.
(Ответить) (Parent) (Thread)
[User Picture]From: bugabuga
2007-07-08 01:03 am
Для наборов вида N1 N2 N3 ... 1, из которых можно представить любую сумму, достаточным условием неоптимальности жадного алгоритма будет:
Разница номиналов любой пары последующих монет (N1 < N2) меньше чем N2*2 :)
В таких случаях нежадный алгоритм может построить сумму N2*2 взяв две монетки N2. А жадный алгоритм всегда будет использовать N1 + a*N3 + b*N4 .... что будет 3 или более монет.

Осталось понять как написать математическое доказательство. Тупею от года в год :(
(Ответить) (Thread)
[User Picture]From: bugabuga
2007-07-08 01:06 am
p.s. ах да, и N1 + N3 != N2 :) но если даже равно то будет просто равный результат для жадного и нежадного
(Ответить) (Parent) (Thread)
[User Picture]From: juan_gandhi
2007-07-08 05:53 am
Ну тут прямо филиал misc.

Кстати, пославший задачу - автор сайта advogato.org.
(Ответить) (Thread)
From: sply
2007-07-08 05:31 pm
Принадлежность к группе оптимального жадного - каждый K(i) должен быть >= S(i-1) и <= 2*S(i-1), где S(n) = сумма K(0)..K(n)

Нутром чую, доказать не могу, тесты подтверждают.
(Ответить) (Thread)
From: sply
2007-07-08 05:52 pm
и оптимальная середина, которая даст наименьшие наборы для всех исел - ряд k(i) = 2^i.
(Ответить) (Parent) (Thread)
[User Picture]From: knop
2007-07-09 08:40 am

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

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

Я чего-то не понимаю, или условие "любую сумму можно собрать из монет данного набора" эквивалентно условию "в данном наборе есть монета достоинством 1 тугрик"?
(Ответить) (Thread)
[User Picture]From: avva
2007-07-12 05:17 pm
да
(Ответить) (Parent) (Thread)