Решение
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.) Если в месяц продается только один вид оборудования, в каком оптимальном порядке их следует продавать? Как выяс- няется, существуют ситуации, в которых оптимальное решение не упорядочивает
коэффициенты по возрастанию или убыванию (как с входными данными )·
Еще по теме Решение:
- § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
- РЕШЕНИЕ
- РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
- ПРИНЯТИЕ РЕШЕНИЙ
- РЕШЕНИЯ КСУ
- Не избегайте принятия решений
- ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
- ЗАДАЧА: РЕШЕНИЕ
- Принять решение
- Управленческие решения
- Решение проблем
- КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.