Задача

В рассматриваемой задаче планирования имеется одна машина, способная обра- батывать задания, и набор заявок {1,2, ..., n}. Ресурсы могут обрабатываться только в период времени от 0 до W (для некоторого числа W).
Каждая заявка представляет собой задание, для обработки которого требуется время w..

Если нашей целью является обработка заданий, при которой обеспечивается максимальная занятость машины до «граничного времени» W, какие задания сле- дует выбрать?

В более формальном виде: имеются n элементов {1, ..., n}, каждому из которых присвоен неотрицательный вес w (для i = 1,...,;?). Также задана граница W. Требу- ется выбрать подмножество S элементов, для которогочтобы этого

ограничения значениебыло как можно больше. Эта задача называется

задачей о сумме подмножеств.

Она является естественным частным случаем более общей задачей, называе- мой задачей о рюкзаке, в которой у каждого элемента i имеется как значение v , так и вес w. Целью в этой общей задачи является нахождение подмножества с макси- мальным суммарным значением, при котором общий вес не превышает W. Название «задача о рюкзаке» происходит от аналогии с наполнением рюкзака емкостью W на максимальную часть объема (или максимальной стоимостью груза) с использова- нием подмножества элементов {1, ..., n}. При упоминании величин w. и Wмы будем использовать термины «вес» и «время».

Поскольку ситуация напоминает другие задачи планирования, уже встречав- шиеся ранее, естественно спросить, можно ли найти оптимальное решение при по- мощи жадного алгоритма. Похоже, ответ на этот вопрос отрицателен — по крайней мере, не известно никакое эффективное жадное правило, которое всегда строит оп- тимальное решение. Один из естественных жадных методов основан на сортировки элементов по убыванию веса (или по крайней мере для всех элементов с весом, не превышающим W), а затем выборе элементов в этом порядке, пока общий вес остается меньше W. Но если значение W кратно 2, и имеются три элемента с весами {W/2 + 1,W/2,W/2}, этот жадный алгоритм не обеспечит оптимального решения. Также можно провести сортировку по возрастанию веса, а затем проделать то же самое; но этот способ не работает для входных данных вида {1,W/2,W/2}.

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

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

Еще по теме Задача:

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