Разработка алгоритма Неудачная попытка

В случае взвешенного интервального планирования сработала общая стратегия с рассмотрением подзадач, в которых задействованы только первые i заявок. По- пробуем применить эту стратегию в данном случае. Лучшее возможное решение, использующее подмножество заявок {1,...
,i}, будет обозначаться OPT(i) (как это делалось ранее). В задаче взвешенного интервального планирования ключевой момент заключался в том, чтобы сосредоточиться на оптимальном решении O нашей задачи и рассмотреть два случая в зависимости от того, принимается или отвергается последняя заявка n этим оптимальным решением. Как и в том случае, одна из частей следует непосредственно из определения OPT(i).

♦ Если n ⅜ O, то OPT(n) = OPT(n - 1).

Затем необходимо рассмотреть случай, в котором n O. Хотелось бы иметь

простую рекурсию, которая сообщит лучшее возможное значение для решений, содержащих последнюю заявку n. Для взвешенного интервального планирования это было несложно, так как мы могли просто удалить каждую заявку, конфликтую- щую с n. В текущей задаче дело обстоит сложнее. Из принятия заявки n не следует, что какую-то другую заявку нужно отклонить, — а лишь то, что для подмножества принимаемых заявок S Л {1, ..., n - 1} остается меньше свободного веса: вес wn ис- пользуется для принятой заявки n, так что для множества S остальных принимае- мых заявок остается только вес W - wn (рис. 6.10).

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

Еще по теме Разработка алгоритма Неудачная попытка:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Неудачный брак
  3. Неудачный брак
  4. Обратите неудачное выступление в источник своей силы
  5. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  6. Попытка портрета
  7. АЛГОРИТМ
  8. Попытка заглушить чувства алкоголем
  9. АЛГОРИТМ УДАЧИ
  10. Глава 10. Как противостоять попыткам манипуляции.
  11. Отстраненность - попытка говорить отвлеченно.
  12. Алгоритм исцеления:
  13. Обращение к наркотикам —попытка не ощущать то, что мы чувствуем.
  14. Алгоритм избавления от боли
  15. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  16. Алгоритм обработки результатов.
  17. 2. Специфика и алгоритмы работы с источниками.
  18. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.