Решение

Два естественных варианта выбора последовательности покупки — сортировка r. в порядке убывания или возрастания. Сталкиваясь с подобными альтернативами, бывает полезно проработать маленький пример и посмотреть, не снимает ли он по крайней мере один из этих вариантов.
Проверим вариант r1 = 2, r2 = 3 и r3 = 4. Покупка лицензий по возрастанию обеспечивает общую стоимость

100(2 + 32 + 43) = 7500,

тогда как при покупке в порядке убывания получается общая стоимость

100(4 + 32 + 23) = 2100.

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

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

Предположим, имеется оптимальное решение O, отличное от решения S. (Дру- гими словами, S состоит из лицензий, отсортированных по убыванию). Значит, оптимальное решение O должно содержать инверсию, то есть должны существо- вать два смежных месяца t и t + 1, для которых скорость роста цены лицензии, купленной в месяце t (обозначим ее rt), меньше, чем купленной в месяце t + 1 (обозначается rt+1). Следовательно, r < r r

Утверждается, что, поменяв местами эти две покупки, можно строго улучшить оптимальное решение; это противоречит исходному предположению об оптималь- ности O.

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

Если поменять местами эти две покупки, остальные покупки будут иметь оди- наковые цены. В О сумма, уплаченная за два месяца, задействованных в замене, будет равна I ОО(-Н;V,') ∙ С другой стороны, если поменять эти две покупки ме- стами, мы заплатим 1ОО(^., *t* r'^1). Поскольку константа 100 является общей для обоих выражений, нужно показать, что второй множитель больше первого. Итак, мы хотим показать, что


Но последнее неравенство истинно просто потому, что r. > 1 для всех i, а значит, r < r ,.

t t+1

На этом доказательство правильности можно считать завершенным. Время выполнения алгоритма равно O(n log n), поскольку сортировка занимает именно такое время, а остальные операции (вывод) выполняются за линейное время. Итак, общее время выполнения равно O(n log n).

Примечание: интересно, что даже при небольшом изменении вопроса ситуация существенно усложняется. Предположим, вместо покупки лицензий с возрастаю- щей ценой вы пытаетесь продавать оборудование, цена которого последовательно снижается. Цена элемента i снижается с коэффициентом г < 1 в месяц, начиная с $ 100, так что при продаже его через t месяцев вы получите (Иначе говоря,

скорость роста теперь не больше, а меньше 1.) Если в месяц продается только один вид оборудования, в каком оптимальном порядке их следует продавать? Как выяс- няется, существуют ситуации, в которых оптимальное решение не упорядочивает

коэффициенты по возрастанию или убыванию (как с входными данными )·

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Решение:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.