Книга «Алгоритмы на практике»

Привет, Хаброжители!

«Алгоритмы на практике» научат решать самые трудные и интересные программистские задачи, а также разрабатывать собственные алгоритмы. В качестве примеров для обучения взяты реальные задания с международных соревнований по программированию. Вы узнаете, как классифицировать задачи, правильно подбирать структуру данных и выбирать алгоритм для решения. Поймете, что выбор структуры данных — будь то хеш-таблица, куча или дерево — влияет на скорость выполнения программы и на эффективность алгоритма. Разберетесь, как применять рекурсию, динамическое программирование, двоичный поиск.

Никакого условного псевдокода, все примеры сопровождаются исходным кодом на языке Си подробными объяснениями.

Для кого эта книга

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

Весь код в книге написан на языке программирования Cи. Но это не учебник по Cи. Если у вас уже есть опыт работы с Си или C++, то смело окунайтесь в материал. Если же вы знакомы только с такими языками, как Java или Python, то я думаю, что большую часть необходимого вы уясните по ходу чтения. Но все же желательно разобрать некоторые концепции Cи заранее или при первой необходимости. В частности, я буду использовать указатели и динамическое выделение памяти. Поэтому, независимо от имеющегося опыта, вам может потребоваться освежить эти темы в памяти.

Лучшая, на мой взгляд, книга по работе с Cи — это второе издание C Programming: A Modern Approach К. Н. Кинга (K. N. King). Даже если вы хорошо знакомы с Cи, все равно рекомендую ее прочесть. Она оказывается отличным помощником, когда особенности этого языка вызывают сложности в понимании кода.

Мемоизация и динамическое программирование

Мы решили задачу про Гомера и бургеры за четыре шага. Во-первых, описали оптимальное решение; во-вторых, написали рекурсивное решение; в-третьих, добавили мемоизацию; в-четвертых, избавились от рекурсии за счет явного решения подзадач в порядке возрастания. Эти четыре шага составляют общий план выработки решений для многих других оптимизационных задач.

Шаг 1. Структура оптимальных решений

На первом шаге нужно разделить оптимальное решение задачи на оптимальные решения подзадач. В «Страсти к бургерам» мы сделали это, поставив вопрос, какой бургер Гомер съест последним. Будет ли это m-минутный бургер? В этом случае останется подзадача заполнения t – m минут. Если же это будет n-минутный бургер, то останется подзадача заполнения t – n минут. Конечно, мы не знаем заранее, какой бургер будет последним, но можно решить эти две подзадачи и выяснить.

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

Когда в задаче с бургерами предполагается, что в оптимальном решении последним бургером будет m-минутный, мы заявляем, что решение для подзадачи t – m будет частью общей задачи t. Более того, оптимальное решение для t должно включать оптимальное решение для t – m: если это условие не выполнить, то решение для t просто не окажется оптимальным, так как его можно улучшить, используя более эффективное решение для t – m. С помощью той же логики можно показать, что если последним бургером в оптимальном решении будет n-минутный, то оставшиеся t – n минут должны быть заполнены путем оптимального решения для t – n.

Позвольте прояснить все сказанное на примере. Предположим, что m = 4, n = 9 и t = 54. Значение оптимального решения равно 11. Существует оптимальное решение S, в котором последним бургером является 9-минутный. Я утверждаю, что S должно состоять из этого 9-минутного бургера при оптимальном решении для 45 минут. Оптимальное решение для 45 минут — 10 бургеров. Если бы S использовало некое субоптимальное решение для первых 45 минут, то S не было бы оптимальным для 11 бургеров. Например, если б для первых 45 минут субоптимальное решение было 5 бургеров, то общее количество бургеров в S было бы всего 6.

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

Я читал и слышал утверждения, что решение оптимизационных задач с помощью мемоизации или динамического программирования стереотипно. И, если вы видели одну такую задачу, то можете считать, что видели все, а при встрече новой достаточно будет просто «щелкнуть пальцами». Я с этим не согласен. Такая точка зрения противоречит практике реализации как начального этапа описания структуры оптимальных решений, так и определения, окажется ли выбранная структура эффективной.

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

Шаг 2. Рекурсивное решение

Шаг 1 предполагает, что не только мемоизация и динамическое программирование могут привести к решению; он оставляет возможность применения также и рекурсивного подхода. Попробуйте найти оптимальное решение с помощью каждой из этих возможностей, решая подзадачи с помощью рекурсии. В задаче с бургерами мы приняли, что оптимальное решение для t минут может состоять из m-минутного бургера и оптимального решения для t – m минут либо из n-минутного бургера и оптимального решения для t – n минут. В связи с этим необходимо решить подзадачи t – m и t – n, а поскольку они меньше, чем t, для них можно использовать рекурсию. Как правило, количество рекурсивных вызовов зависит от числа кандидатов, соревнующихся на звание оптимального решения.

Шаг 3. Мемоизация

Если мы преуспеем на предыдущем шаге, значит, у нас будет верное решение задачи. Хотя, как мы видели из задачи про бургеры, такое решение может потребовать совершенно неоправданных затрат времени на выполнение. Причина в том, что одни и те же подзадачи решаются снова и снова, порождая явление, называемое наложением подзадач. На самом деле, не будь проблемы с наложением, можно было бы остановиться и здесь: рекурсия нас вполне бы устроила. Вспомните главу 2 и две задачи, которые в ней решались. Тогда мы вполне обошлись рекурсией, которая сработала эффективно, потому что каждая подзадача решалась по одному разу. К примеру, в задаче про сбор конфет мы вычисляли общее количество конфет в дереве. Две подзадачи выясняли общее число конфет в левом и правом поддеревьях. В том случае они не зависели друг от друга, то есть для решения подзадачи левого поддерева не требовались данные из правого и наоборот.

Если наложения подзадач нет, можно ограничиться использованием рекурсии. Если же наложение присутствует, настает черед мемоизации. Как мы видели в задаче с Гомером, мемоизация подразумевает сохранение ответа подзадачи при ее первичном решении. Если этот ответ понадобится в дальнейшем, его находят в массиве, но не вычисляют повторно. Да, подзадачи по-прежнему накладываются, но решаются они в этом случае только один раз.

Шаг 4. Динамическое программирование

Скорее всего, решение, полученное на третьем шаге, окажется достаточно быстрым. Такое решение продолжает использовать рекурсию, но уже без риска повторения одной и той же работы. Однако, как будет показано ниже, иногда требуется избавиться от рекурсии. Добиться этого можно за счет систематического решения подзадач в порядке их возрастания от самых малых до самых больших. Это и называется динамическим программированием — использование цикла вместо рекурсии для явного последовательного решения подзадач.

Так что же лучше: мемоизация или динамическое программирование? Для многих задач они примерно равнозначны, и в таких случаях можно выбирать, исходя из личных предпочтений. Я предпочитаю мемоизацию. Далее в главе будет пример (задача 3), где таблицы memo и dp имеют более двух измерений. В подобных задачах я зачастую с трудом нахожу все базовые случаи и определяю границы таблицы dp.

Мемоизация используется по мере необходимости. Рассмотрим тестовый пример из «Страсти к бургерам», в котором у нас есть 2-минутный и 4-минутный бургеры и 90 минут времени. Решение с мемоизацией не будет обрабатывать нечетные значения времени, такие как 89, 87 или 85 минут, потому что такие подзадачи не возникнут при вычитании из 90 произведений двоек или четверок. Динамическое программирование, наоборот, решает все подзадачи до достижения 90. Кажется, что мемоизация должна обеспечивать преимущества: в самом деле, если огромные пространства подзадач не используются, тогда мемоизация будет быстрее динамического программирования. Но нужно учесть дополнительную нагрузку, возникающую при использовании рекурсии со всеми вызовами и возвращениями из функций. Если вам захочется выяснить истину, то просто напишите код для обоих вариантов решения и сравните их скорость.

Нередко разработчики описывают решения с мемоизацией как нисходящие, а решения с динамическим программированием как восходящие. «Нисходящими» они называются, потому что для решения больших подзадач мы рекурсивно переходим вниз к меньшим подзадачам. В «восходящих» же решениях мы, наоборот, начинаем снизу — с меньших подзадач — и продвигаемся наверх.

Лично меня увлекают и мемоизация, и динамическое программирование. С их помощью можно решать множество задач разных видов. Мне неизвестны другие столь же эффективные методы построения алгоритмов. Многие инструменты, которые мы изучаем в этой книге, например хеш-таблицы из главы 1, позволяют ускорять вычисления. Но задачи можно решать вообще без этих инструментов — конечно, не за то время, которое устанавливается при соревнованиях, но все равно достаточно быстро для эффективного практического применения. Тем не менее мемоизация и динамическое программирование имеют важные преимущества. Они улучшают рекурсивные подходы, преобразуя на удивление медленные алгоритмы в невероятно быстрые. Надеюсь, что в оставшейся части главы мне удастся увлечь вас этими методами, так чтобы интерес сохранился и после завершения чтения.

Задача 2. Экономные покупатели

В «Страсти к бургерам» нам удалось решить задачу, рассматривая только по две подзадачи. Здесь же мы увидим, что каждая подзадача может требовать более тщательной проработки.

Рассмотрим задачу с платформы UV под номером 10980.

Условие

Вы хотите купить яблоки в магазине. На яблоки установлена фиксированная цена, к примеру $1.75 за штуку. Помимо этого, у магазина есть m ценовых схем, в каждой из которых установлена стоимость p за n яблок. Например, в одной схеме три яблока стоят $4.00, в другой схеме два яблока стоят $2.50. Вам нужно купить не менее k яблок по наименьшей цене.

Входные данные

Каждый тестовый пример состоит из следующих строк:

• Цена за одно яблоко и число ценовых схем m для данного примера. Максимальное значение m равно 20.
• m строк, в каждой из которых указано число яблок n и их общая стоимость p. Значение n находится в диапазоне между 1 и 100.
• Строки с числами k, указывающими количество яблок, которое нужно купить. Их значения находятся между 0 и 100.

Каждая цена во входных данных представлена числом с плавающей точкой и имеет два десятичных знака.

В описании задачи я привел в качестве примера цены за яблоко $1.75. Помимо этого, приведены две ценовые схемы: три яблока за $4.00 и два яблока за $2.50. Предположим, что нужно определить минимальные стоимости при покупке не менее одного и при покупке не менее четырех яблок. Вот входные данные для этого примера:

1.75 2
3 4.00
2 2.50
1 4

Выходные данные

Для каждого тестового примера требуется вывести следующее:

• Номер примера Case c:, где с является номером тестового примера, отсчет номеров начинается с 1.
• Для каждого числа k — фразу Buy k for $d (купить k за $d), где d будет самым дешевым вариантом покупки не менее k яблок.

Вот каким будет вывод для приведенных выше входных данных:

Case 1:
Buy 1 for $1.75
Buy 4 for $5.00

Время на решение всех тестовых примеров — три секунды.

Описание оптимального решения

Условие задачи гласит, что нужно купить не менее k яблок по минимальной цене. Это означает, что покупка k яблок не является единственным вариантом: можно купить и больше, если это окажется дешевле. Начнем с попытки решить задачу для k яблок во многом аналогично тому, как мы делали в задаче с бургерами. Тогда мы нашли способ при необходимости переходить от ровно t минут к их меньшему числу. Будем надеяться, что нам удастся проделать аналогичное и здесь, начав с k яблок и определив самую низкую стоимость для k, k + 1, k + 2 и т. д. Если ничего вдруг не сломается…

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

Что лучше: купить три яблока за $4.00 (схема 1) или два за $2.50 (схема 2)? На этот вопрос можно попробовать ответить, вычислив стоимость одного яблока для каждой из предложенных схем. В схеме 1 получится $4.00/3 = $1.33 за яблоко, а в схеме 2 каждое яблоко выйдет по $2.50/2 = $1.25. Похоже, что схема 2 выгоднее схемы 1. Давайте также предположим, что можем просто купить одно яблоко за $1.75. Таким образом, у нас получится последовательность чисел от наименьшей до самой высокой стоимости яблока: $1.25, $1.33, $1.75.

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

Если бы мы хотели купить ровно четыре яблока в предложенном примере, то начали бы со схемы 2, потому что она позволяет приобрести их по наилучшей цене за штуку. Использование схемы 2 один раз означает покупку двух яблок за $2.50, после чего остается купить еще два. Можно снова использовать эту же схему и приобрести еще пару яблок, потратив дополнительно $2.50. В этом случае мы заплатим за четыре яблока $5.00 и получим лучший результат.

Обратите внимание, что интуитивной оценки алгоритма и его эффективности в одном тестовом примере недостаточно, чтобы сделать заключение о том, насколько он верен. Алгоритм, основанный на использовании наименьшей стоимости яблока, имеет недостаток, что можно доказать на примерах. Попробуйте самостоятельно найти такие случаи, прежде чем продолжать чтение.

Рассмотрим такой пример. Предположим, что мы хотим купить три яблока, а не четыре. Мы снова начинаем со схемы 2, которая дает нам два яблока за $2.50. Теперь нужно купить всего одно яблоко, и единственный вариант — это заплатить за него $1.75. Тогда общая стоимость составит $4.25. Но есть способ получше — нужно использовать схему 1, затратив всего $4.00. Так мы избавимся от необходимости платить высокую цену за одно дополнительное яблоко.

Возникает желание дополнить наш алгоритм корректирующими его правилами. Например, «если существует ценовая схема ровно для нужного количества яблок, то следует использовать ее». Однако можно легко опровергнуть этот доработанный алгоритм, если добавить во входные данные несколько схем, в которых магазин продает яблоки по сильно завышенным ценам, например три яблока за $100.00.

При использовании мемоизации и динамического программирования в поиске наилучшего решения мы пробуем все возможные варианты, после чего выбираем наилучший. Вспомните задачу с бургерами. Должен ли Гомер закончить трапезу на m-минутном или n-минутном бургере? Ответа мы не знаем, поэтому пробуем оба варианта. В противоположность этому, жадный алгоритм не перебирает большое число вариантов, а пробует только один. Использование наилучшей цены яблока, как мы сделали выше, является примером жадного алгоритма, потому что на каждом шаге он выбирает действие без рассмотрения других вариантов. Иногда жадные алгоритмы работают. Более того, поскольку они зачастую выполняются быстрее и легче реализуются, то могут быть более эффективными, чем алгоритмы с динамическим программированием. Для данной же задачи жадные алгоритмы — как опробованный выше, так и любые другие — недостаточно эффективны.

В задаче с бургерами мы рассуждали, что если можно есть бургеры в течение ровно t минут, то последним бургером в оптимальном решении окажется n-минутный или m-минутный. Подобным образом, для текущей задачи нам нужно предположить, что оптимальное решение для покупки k яблок должно оканчиваться одним из нескольких возможных вариантов. Вот утверждение: если доступной ценовой схемой является схема 1, схема 2, …, схема m, тогда последним нашим действием должно быть использование одной из этих m ценовых схем. Других вариантов у нас нет, ведь так?

Вообще-то не совсем. Последним действием в оптимальном решении может стать покупка и одного яблока. Этот вариант доступен нам всегда. Вместо того чтобы решать две подзадачи, как в разделе с бургерами, мы решим m + 1 подзадач: по одной для каждой из m ценовых схем и дополнительную для покупки одного яблока.

Предположим, что оптимальное решение для покупки k яблок оканчивается тратой p долларов на n яблок. Тогда нужно купить k – n яблок и прибавить их стоимость к p. При этом важно проверить, что общее оптимальное решение для k яблок содержит в себе оптимальное решение для k – n яблок. Таково требование к оптимальной подструктуре для мемоизации и динамического программирования. Как и в «Страсти к бургерам», оптимальная подструктура необходима. Если решение для k не использует оптимальное решение для k – n, тогда оно не сможет быть оптимальным, так как не окажется в той же степени эффективным, в какой было бы при использовании оптимального решения для k – n.

Конечно же, мы заранее не знаем, какое действие предпримем в решении последним, чтобы оно оказалось оптимальным. Используем ли мы схему 1, схему 2, схему 3 или купим одно яблоко? Кто вообще это знает? Как и в любом алгоритме с мемоизацией или динамическим программированием, мы пробуем все варианты и выбираем наилучший.

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

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

Решение 1. Рекурсия

Как и в задаче с бургерами, первым делом нужно написать вспомогательную функцию.

Вспомогательная функция: решение для заданного числа яблок

Напишем функцию solve_k, которая будет аналогична solve_t из задачи «Страсть к бургерам». Вот ее заголовок:

double solve_k(int num[], double price[], int num_schemes,
               double unit_price, int num_items)

Ее параметры:

• num — массив чисел яблок в ценовых схемах, по одному элементу для каждой схемы. К примеру, если даны две ценовые схемы, первая для трех яблок и вторая для двух, то массив будет выглядеть как [3, 2].
• price — массив цен, по одному элементу для каждой схемы. К примеру, если даны две ценовые схемы, первая со стоимостью 4.00 и вторая со стоимостью 2.50, то массив будет выглядеть как [4.00, 2.50]. Обратите внимание, что num и price вместе предоставляют исчерпывающую информацию о ценовых схемах.
• num_schemes — количество ценовых схем. Это значение m из тестового примера.
• unit_price — цена одного яблока.
• num_items — количество яблок, которое нужно купить.

Функция solve_k возвращает минимальную цену num_items яблок.

Код solve_k приведен в листинге 3.9. При ознакомлении с ним я настоятельно рекомендую вам сравнить его с solve_t из листинга 3.1 задачи про бургеры. Какие отличия вы сможете найти? Чем они обусловлены? Решения с мемоизацией и динамическим программированием используют одинаковую структуру кода. Если нам удастся освоить эту структуру, то можно будет сосредоточиться на отличиях и специфике каждой задачи.

Листинг 3.9. Решение для num_items элементов

double min(double v1, double v2) { ❶
   if (v1 < v2)
      return v1;
   else
      return v2;
}

double solve_k(int num[], double price[], int num_schemes,
               double unit_price, int num_items) {
   double best, result;
   int i;
   if (num_items == 0) ❷
      return 0; ❸
   else {
      result = solve_k(num, price, num_schemes, unit_price, ❹
                       num_items - 1);
      best = result + unit_price; ❺
      for (i = 0; i < num_schemes; i++)
         if (num_items - num[i] >= 0) { ❻
         result = solve_k(num, price, num_schemes, unit_price, ❼
                          num_items - num[i]);
         best = min(best, result + price[i]); ❽
      }
         return best;
   }
}

Код начинается с небольшой функции min ❶: она нужна для сравнения решений и выбора наименьшего. В задаче с бургерами мы использовали аналогичную функцию max, так как искали максимальное количество бургеров. Здесь же нас интересует минимальная стоимость. Оптимизационные задачи могут быть задачами как по максимизации («Страсть к бургерам»), так и по минимизации («Экономные покупатели») — внимательно читайте условия, чтобы убедиться в правильности выбора направления оптимизации.

Что мы делаем, если нужно решить задачу для 0 яблок ❷? Возвращаем 0 ❸, потому что минимальная стоимость покупки нуля яблок равна $0.00. Базовыми случаями являются ноль затраченных на еду минут для задачи с бургерами и ноль купленных яблок в текущей задаче. Как всегда при применении рекурсии, любой задаче по оптимизации требуется хотя бы один базовый случай.

Если условие базового случая не выполняется, значит, num_items является положительным целым числом и потребуется найти оптимальный способ покупки ровно такого количества яблок. Для отслеживания наилучшего найденного на данный момент варианта (наименьшей стоимости) используется переменная best.

Один из способов — это оптимально решать задачу для num_items – 1 яблок ❹ и прибавлять стоимость конечного яблока ❺.

Теперь становится очевидным значительное структурное отличие этой задачи от задачи с бургерами, которое заключается в наличии цикла внутри рекурсивной функции. В «Страсти к бургерам» цикл не требовался, потому что решить нужно было всего две подзадачи. Мы просто пробовали первую и следом вторую. Здесь же каждой ценовой схеме соответствует своя подзадача, и нужно перебрать их все.

Мы выполняем проверку, может ли вообще использоваться текущая ценовая схема ❻: если ее количество яблок не больше нужного, то схему можно пробовать. Далее совершается рекурсивный вызов для решения подзадачи, которая получается после вычитания количества яблок, соответствующего данной ценовой схеме ❼ (это действие аналогично более раннему рекурсивному вызову, в котором мы отнимали единицу ❹). Если решение этой подзадачи в сумме с ценой текущей схемы оказывается на данный момент лучшим вариантом, best соответствующим образом обновляется ❽.

Функция solve

Мы добились оптимального решения для k яблок, но в условии задачи есть одна деталь, с который мы еще не разобрались: «Нам нужно купить не менее k яблок, затратив минимальное количество средств». Почему вообще важна эта разница между ровно k яблоками и «не менее k яблок»? Сможете ли вы найти тестовый пример, в котором более k яблок окажутся дешевле, чем k?

Вот один такой вариант. Предположим, что одно яблоко стоит $1.75. Даны две ценовые схемы: по схеме 1 можно купить четыре яблока за $3.00, а по схеме 2 два яблока стоят $2.00. Нам нужно купить не менее трех яблок. Входные данные этого примера выглядят так:

1.75 2
4 3.00
2 2.00
3

Самый дешевый способ купить три яблока — это потратить $3.75: $1.75 за одно яблоко и $2.00 за два согласно схеме 2. Однако можно потратить и меньше, если купить сразу четыре яблока, а не три. Для этого нужно просто воспользоваться ценовой схемой 1, что будет стоить всего $3.00. Таким образом, верный вывод для данного кейса будет:

Case 1:
Buy 3 for $3.00

Хотя на деле покупается четыре яблока, а не три, вывод Buy 3 будет верен. По условиям задачи всегда выводится минимальное число яблок, которое требуется купить, независимо от того, сколько было куплено по факту с целью экономии денег.

Далее нам понадобится функция solve, подобная той, что была в листинге 3.2 задачи про бургеры. Тогда мы перебирали значения по убыванию, пока не находили решение. Здесь же мы будем перебирать значения по возрастанию, отслеживая по ходу процесса минимум. Вот первый вариант кода:

double solve(int num[], double price[], int num_schemes,
             double unit_price, int num_items) {
   double best;
   int i;
   best = solve_k(num, price, num_schemes, ❶
                  unit_price, num_items);
   for (i = num_items + 1; i < ???; i++) ❷
      best = min(best, solve_k(num, price, num_schemes,
                               unit_price, i));
   return best;
}

Мы инициализируем best с оптимальным числом для покупки ровно num_items яблок ❶. Далее с помощью цикла for выполняется перебор количества яблок по возрастанию ❷. Цикл for останавливается, когда… Так. А откуда нам знать, что уже можно остановиться? Возможно, нужно купить 3 яблока, но самым дешевым вариантом будет покупка 4, 5, 10 или даже 20. Такой проблемы в задаче с бургерами не было, потому что там мы спускались вниз по направлению к нулю, а не поднимались.

Спасает нас то, что максимальное число яблок в ценовой схеме не может превышать 100. Но чем это поможет?

Предположим, что нужно купить не менее 50 яблок. Может ли покупка 60 штук оказаться оптимальным вариантом? Конечно! Возможно, последняя ценовая схема в наилучшем решении для 60 яблок будет состоять из 20 штук. Тогда можно будет совместить эти 20 яблок с оптимальным решением для 40 яблок и в общем получить 60.

Снова предположим, что нужно купить 50 яблок. Будет ли иметь смысл приобретение 180? Что ж, подумаем о возможном оптимальном решении. Наибольшая возможная ценовая схема может быть предложена для 100 яблок. Прежде чем ее использовать, нам бы пришлось купить не менее 80 яблок, которые были бы дешевле, чем 180. Но 80 уже больше 50. Следовательно, купить 80 яблок выгоднее, чем 180. Значит, покупка 180 яблок не может быть оптимальным решением, если их нужно всего 50.

На самом деле, для 50 яблок максимальным количеством, которое вообще есть смысл рассматривать, является 149. Если покупать 150 или более яблок, то вычитание последней ценовой схемы гарантированно даст более дешевый способ купить 50 или более яблок.
Условия задачи устанавливают равным 100 не только максимальное число яблок в ценовой схеме, но также наибольший возможный объем их покупки. В случае, когда нужно приобрести 100 яблок, максимальным рассматриваемым числом должно стать 100 + 99 = 199. Объединение всех этих умозаключений дает нам функцию solve, которая приведена в листинге 3.10.

Листинг 3.10. Решение 1

#define SIZE 200

double solve(int num[], double price[], int num_schemes,
             double unit_price, int num_items) {
   double best;
   int i;
   best = solve_k(num, price, num_schemes, unit_price, num_items);
   for (i = num_items + 1; i < SIZE; i++)
      best = min(best, solve_k(num, price, num_schemes,
                               unit_price, i));
   return best;
}

Теперь нам нужна только функция main, и можно будет отправлять результаты на проверку.

Об авторе

Даниэль Зингаро — доцент кафедры информатики в Университете Торонто, он неоднократно награждался за выдающиеся успехи в преподавании. Основная область его научных интересов — особенности обучения компьютерным наукам: он исследует, как студенты усваивают (а иногда не усваивают) материал в сфере computer science.

О научном редакторе

Ларри Юли Чжан — доцент кафедры информатики в Университете Торонто. Область его преподавательских и исследовательских интересов включает алгоритмы, структуры данных, операционные системы, компьютерные сети, социальные сети и компьютерное образование. Он состоял в программных комитетах конференций ACM SIGCSE, ACM ITiCSE и WCCCE.

Более подробно с книгой можно ознакомиться на сайте издательства:
» Оглавление
» Отрывок

По факту оплаты бумажной версии книги на e-mail высылается электронная книга.
Для Хаброжителей скидка 25% по купону — Алгоритмы