Вор пробрался в лавку специй и нашёл там четыре фунта шафрана, три фунта ванили и пять фунтов корицы. В его рюкзак можно сложить до девяти фунтов, поэтому забрать всё он не сможет. Предположим, что цены на шафран, ваниль и корицу $5000, $200 и $10 соответственно. Как унести максимально дорогую добычу? Если вор заберёт фунтов шафрана, фунтов ванили и фунтов корицы, общая ценность украденного составит . Вор хотел бы найти максимальное значение этого выражения при следующих ограничениях: , , , .
- Входные данные: Первая строка ввода содержит специй и вместимость рюкзака . Следующие строк указывают цену и вес специй. -я строка включает в себя цену и вес -й специи.
- Выходные данные: Максимальное значение специй, которые вместятся в рюкзак.
- Ограничения: , ; , для всех . Все числа — целые.
- В дополнение: Хотя ввод для этой задачи состоит из целых чисел, вывести необходимо нецелое число. Таким образом, абсолютное значение разницы между ответом вашей программы и оптимальным значением не должно превышать . Для этого ваш ответ должен содержать не меньше четырёх цифр в дробной части (иначе даже правильно вычисленный ответ может стать неправильным из-за проблем с округлением).
Пример 1
|
Ввод |
Вывод |
|
3 50 |
180.0000 |
Чтобы получить значение , вор возьмёт и первую, и третью специи полностью.
Пример 2
|
Ввод |
Вывод |
|
1 10 |
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)
Время выполнения. Время выполнения этого алгоритма — . При каждой итерации сканируется список специй и находится самая дорогая. Максимальное количество итераций — , так как каждая итерация снижает количество рассматриваемых специй.