Численные задачи

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

♦ Задача о суммировании подмножеств: задано множество натуральных чисел w1, ..., wn и целевое число W.

Существует ли подмножество {wp ..., wn}, сумма которого равна ровно W?

Естественно попытаться применить сведение из задачи о суммировании под- множеств, когда имеется задача со взвешенными объектами, а целью является вы- бор объектов с учетом некоторого ограничения на общий вес выбранных объектов. Например, именно это происходит в доказательстве (8.24) при демонстрации NP- полноты планирования с временем доступности и предельным временем.

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

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

Еще по теме Численные задачи:

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