Вор пробрался в лавку специй и нашёл там четыре фунта шафрана, три фунта ванили и пять фунтов корицы. В его рюкзак можно сложить до девяти фунтов, поэтому забрать всё он не сможет. Предположим, что цены на шафран, ваниль и корицу $5000, $200 и $10 соответственно. Как унести максимально дорогую добычу? Если вор заберёт $u_1$ фунтов шафрана, $u_2$ фунтов ванили и $u_3$ фунтов корицы, общая ценность украденного составит $5000\cdot \dfrac{u_1}{4} + 200\cdot \dfrac{u_2}{3} + 10\cdot \dfrac{u_3}{5}$. Вор хотел бы найти максимальное значение этого выражения при следующих ограничениях: $u_1 \le 4$, $u_2 \le 3$, $u_3 \le 5$, $u_1+u_2+u_3 \le 9$.
- Входные данные: Первая строка ввода содержит $n$ специй и вместимость рюкзака $W$. Следующие $n$ строк указывают цену и вес специй. $i$-я строка включает в себя цену $c_i$ и вес $w_i$ $i$-й специи.
- Выходные данные: Максимальное значение специй, которые вместятся в рюкзак.
- Ограничения: $1 \le n \le 10^3$, $0 \le W \le 2 \cdot 10^6$; $0 \le c_i \le 2 \cdot 10^6$, $0 < w_i \le 2 \cdot 10^6$ для всех $1 \le i \le n$. Все числа — целые.
- В дополнение: Хотя ввод для этой задачи состоит из целых чисел, вывести необходимо нецелое число. Таким образом, абсолютное значение разницы между ответом вашей программы и оптимальным значением не должно превышать $10^{-3}$. Для этого ваш ответ должен содержать не меньше четырёх цифр в дробной части (иначе даже правильно вычисленный ответ может стать неправильным из-за проблем с округлением).
Пример 1
Ввод | Вывод |
---|---|
3 50 60 20 100 50 120 30 | 180.0000 |
Чтобы получить значение $180$, вор возьмёт и первую, и третью специи полностью.
Пример 2
Ввод | Вывод |
---|---|
1 10 500 30 | 166.6667 |
Вору нужно забрать десять фунтов единственной доступной специи.
Совет: по возможности старайтесь избегать чисел с плавающей дробной частью.
Решение
Определим цену специи $i$ как $\frac{c_i}{w_i}$. Естественной стратегией для вора было бы брать как можно больше самой дорогой специи.
Чтобы доказать, что эта стратегия приводит к оптимальному решению, рассмотрим самую дорогую специю $m$. Каков максимальный объём $a$ $m$-й специи, который вор может положить в рюкзак?
Во-первых, она должна уместиться в рюкзак: $a \le W$.
Во-вторых, она не должна превышать доступный объём $m$-й специи: $a \le w_m$.
Следовательно, $a=\min{w_m, W}$. Мы утверждаем, что существует оптимальное решение, включающее в себя $a$ фунтов $m$-й специи.
Чтобы это доказать, рассмотрим оптимальное решение $u_1,\dotsc,u_n$, при котором мы получаем максимальное количество $u_m$ самой дорогой $m$-й специи из всех оптимальных решений ($u_i$ означает количество $i$-й специи). Если $u_m=a$, то ничего доказывать не нужно. Иначе $u_m \lt a$. Поэтому $u_m \lt w_m$ и $u_m \lt W$.
Рассмотрим два варианта.
- При нынешнем решении $u_1+u_2+\dotsc+u_n \lt W$ рюкзак заполнен не до конца. Так как $u_m \le w_m$, можно взять немного больше $m$-й специи: так, мы получаем новое решение, которое лучше и оптимальнее нынешнего.
- Рюкзак заполнен до конца: $u_1+\dotsc+u_m=W$. Так как $u_m \lt W$, при подборе $i \neq m$ можно получить $u_i \gt 0$. Так, вместо маленького количества $i$-й специи, можно взять такое же количество $m$-й специи. Таким образом мы сохраним общий вес, но увеличим общую ценность и количество самой дорогой $m$-й специи в рюкзаке. Это противоречит идее, что в изначальном решении был максимум $m$-й специи.
Доказав, что мы можем взять самой дорогой специи столько, сколько получится, мы можем спроектировать жадный алгоритм: взять как можно больше самой дорогой специи и повторить. Мы прекратим, когда больше не останется специй или когда рюкзак будет заполнен до конца. В псевдокоде, приведённом ниже, $Weight$ и $Cost$ — массивы, содержащие значения веса и цены.
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)
Время выполнения. Время выполнения этого алгоритма — $O(n^2)$. При каждой итерации сканируется список специй и находится самая дорогая. Максимальное количество итераций — $n$, так как каждая итерация снижает количество рассматриваемых специй.