Задача о сумме подмножеств и задача о рюкзаке: добавление переменной

Мы видим все больше примеров того, что область планирования предоставляет богатый источник алгоритмических задач, обладающих практическим смыслом. Ранее мы рассматривали задачи, в которых заявки задаются интервалом времени, а также задачи, в которых для заявки определяется продолжительность и предель- ное время, но не указывается конкретный интервал времени, в течение которого они должны выполняться.

В этом разделе рассматривается разновидность задач второго типа, с про- должительностями и предельным временем, которую трудно решать напрямую с использованием методов, применявшихся ранее. Для решения задачи будет применен метод динамического программирования, но с небольшими измене- ниями: «очевидного» множества подзадач оказывается недостаточно, и нам при- дется создавать расширенный набор подзадач. Как вы вскоре увидите, для этого в рекуррентное отношение, лежащее в основе динамической программы, будет добавлена новая переменная.

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

Еще по теме Задача о сумме подмножеств и задача о рюкзаке: добавление переменной:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии
  16. Основные задачи МПП.