Упражнение с решением 2

Ваши друзья открывают компанию, занимающуюся компьютерной безопасностью, и им необходимо получить лицензии на n разных криптографических продуктов. Согласно действующим требованиям, они могут получать не более одной лицензии в месяц.

Каждая лицензия в настоящее время стоит $100, но со временем цена растет по экспоненциальному закону: в частности, лицензия j ежемесячно умножается на коэффициент r. > 1 (где r. — заданный параметр). Таким образом, если лицензия j приобретается через t месяцев, она будет стоить 100 · rj. Будем считать, что все скорости роста цены различны, то есть r. ф r. для i ф j (хотя все они начинаются с одной исходной цены $100).

Вопрос: если компания может покупать не более одной лицензии в месяц, в ка- ком порядке следует совершать покупки, чтобы общая потраченная сумма была минимальной?

Приведите алгоритм, который получает n скоростей роста цены r1, r2, ..., rn и вы- числяет порядок покупки лицензий, чтобы общая сумма потраченных денег была минимальной. Время выполнения алгоритма должно быть полиномиальным по n.

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

Еще по теме Упражнение с решением 2:

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