Расширение: задача о рюкзаке

Задача о рюкзаке немного сложнее задачи планирования, которая рассматривалась нами ранее. Возьмем ситуацию, в которой каждому элементу i поставлен в соот- ветствие неотрицательный вес wi, как и прежде, и отдельное значение v.
Цель —

найти подмножество S с максимальным значением .i/,, в котором общий вес множества не превышает W: г ws < W.

Алгоритм динамического программирования несложно расширить до этой более общей задачи. Аналогичное множество подзадач OPT(/, w) используется для представления значения оптимального решения с использованием подмножества элементов {1, ..., /} и максимального доступного веса w. Рассмотрим оптимальное решение O и определим два случая в зависимости от того, выполняется ли условие n e O:

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

♦ Если n O, то OPT(n, W) = vn + OPT(n - 1, W - wn).

Применение этой аргументации к подзадачам приводит к следующей аналогии с (6.8).

(6.11) Е сли w < w^, то OPT(/, w) = OPT(/ - 1, w). В противном случае OPT(/, w) = max(OPT(/ - 1, w), v. + OPT(/ - 1, w - w.)).

При помощи этого рекуррентного отношения можно записать полностью анало- гичный алгоритм динамического программирования, из чего вытекает следующий факт:

(6.12) Задача о рюкзаке решается за время O(nW).

6.5.

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

Еще по теме Расширение: задача о рюкзаке:

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