Здесь, похоже, проходит тот же трюк, что и при обосновании алгоритма проверки алфавитного кодирования на однозначность (то есть проверки гомоморфизма свободных полугрупп на инъективность).
Пусть задан конечный набор монет целочисленного достоинства, где 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.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
оценка
Date: 2007-07-08 12:27 am (UTC)Пусть задан конечный набор монет целочисленного достоинства, где 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