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

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

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

Пример 1Пример 1

Ввод	Вывод
3 50 60 20 100 50 120 30	180.0000

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

Пример 2Пример 2

Ввод	Вывод
1 10 500 30	166.6667

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

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

РешениеРешение

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

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

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

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

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

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

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

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

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

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

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