7.2. Задача «Специи»

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

Ключевые вопросы параграфа

• Как работает жадный алгоритм в задаче выбора по критерию «цена за единицу веса»?
• Почему важно доказывать корректность жадной стратегии, даже если она кажется очевидной?
• Как оформить решение, чтобы избежать ошибок округления и сохранить точность при работе с вещественными числами?

Выбор предметов с наибольшей ценностью при ограниченной вместимости

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

Предположим, что цены на шафран, ваниль и корицу $5000, $200 и $10 соответственно. Как унести максимально дорогую добычу? Если вор заберёт фунтов шафрана, фунтов ванили и фунтов корицы, общая ценность украденного составит . Вор хотел бы найти максимальное значение этого выражения при следующих ограничениях: , , , .

• Входные данные: Первая строка ввода содержит специй и вместимость рюкзака . Следующие строк указывают цену и вес специй. -я строка включает в себя цену и вес -й специи.
• Выходные данные: Максимальное значение специй, которые вместятся в рюкзак.
• Ограничения: , ; , для всех . Все числа — целые.
• В дополнение: Хотя ввод для этой задачи состоит из целых чисел, вывести необходимо нецелое число. Таким образом, абсолютное значение разницы между ответом вашей программы и оптимальным значением не должно превышать . Для этого ваш ответ должен содержать не меньше четырёх цифр в дробной части (иначе даже правильно вычисленный ответ может стать неправильным из-за проблем с округлением).

Пример 1

Чтобы получить значение , вор возьмёт и первую, и третью специи полностью.

Пример 2

Вору нужно забрать десять фунтов единственной доступной специи.

Совет: по возможности старайтесь избегать чисел с плавающей дробной частью.

Решение

Определим стоимость специи как . Естественной стратегией для вора было бы брать как можно больше самой дорогой специи.

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

Во-первых, она должна уместиться в рюкзак: .

Во-вторых, она не должна превышать доступный объём -й специи: .

Следовательно, . Мы утверждаем, что существует оптимальное решение, включающее в себя фунтов -й специи.

Чтобы это доказать, рассмотрим оптимальное решение , при котором мы получаем максимальное количество самой дорогой -й специи из всех оптимальных решений ( означает количество -й специи). Если , то ничего доказывать не нужно. Иначе . Поэтому и .

Рассмотрим два варианта.

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

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

1MaximumLoot(W, Weight, Cost)
2    if W=0 or Weight is empty:
3        return 0
4    m = the index of the most expensive item
5    amount = min(Weight[m], W)
6    value = Cost[m] / Weight[m] * amount
7    remove the m-th element from Weight and Cost
8    return value + MaximumLoot(W - amount, Weight, Cost)

Время выполнения. Время выполнения этого алгоритма — . При каждой итерации сканируется список специй и находится самая дорогая. Максимальное количество итераций — , так как каждая итерация снижает количество рассматриваемых специй.

Что дальше

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

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

А пока вы не ушли дальше — закрепите материал на практике:

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

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

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