Задача
Если нашей целью является обработка заданий, при которой обеспечивается максимальная занятость машины до «граничного времени» 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}.
В этом разделе мы постараемся показать, как применить динамическое програм- мирование для решения задачи. Вспомните основные принципы динамического программирования: нужно перейти к небольшому количеству подзадач, чтобы каждая подзадача легко решалась по «меньшим» подзадачам, а решение исходной задачи легко строилось по известным решениям всех подзадач. Проблема в том, чтобы определить хорошее множество подзадач.
Еще по теме Задача:
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА
- ЗАДАЧА: РЕШЕНИЕ
- Основные задачи.
- в) Задачи
- в) Задачи
- ПСИХОАНАЛИЗ: ЗАДАЧА
- ЗАДАЧА ДВИГАТЕЛЬНАЯ
- Основные задачи
- Правило решаемой психологической задачи.
- Задачи и упражнения
- Терапевтическая задача
- 3. Задачи и функции социологии
- Основные задачи МПП.
- Задачи и упражнения
- Задачи
- Трудная задача