<<
>>

Разработка алгоритма

В разделе 6.4 рассматривались алгоритмы для задачи о сумме подмножеств — частного случая задачи о рюкзаке, в котором v = w для всех элементов i. Для этого частного случая был предложен алгоритм динамического программирования, вы- полнявшийся за время O(nW) при условии, что веса являются целыми числами.
Алгоритм естественным образом расширяется на более общую задачу о рюкзаке (см. конец раздела 6.4). Алгоритм, приведенный в разделе 6.4, хорошо работает для малых весов (даже если значения велики). Также возможно определить алго- ритм динамического программирования для случая с малыми значениями (даже при больших весах). В конце раздела приводится алгоритм динамического про- граммирования для этого случая, выполняемый за время O(nV), где v* = max v . Учтите, что этот алгоритм не выполняется за полиномиальное время: он только псевдополиномиален из-за зависимости от размера значений v.. Так как А/⅛олнота этой задачи была доказана в главе 8, не стоит рассчитывать, что нам удастся найти алгоритм с полиномиальным временем.

Алгоритмы с псевдополиномиальной зависимостью от значений часто могут использоваться для разработки схем аппроксимации с полиномиальным временем, и разработанный нами алгоритм очень наглядно демонстрирует эту базовую стра- тегию. В частности, мы используем алгоритм динамического программирования с временем выполнения O(n2v*) для разработки схемы аппроксимации с полино- миальным временем: если значения являются малыми целыми числами, то значе- ние v* мало, а задача уже может быть решена за полиномиальное время. С другой стороны, если значения велики, то нам не обязательно работать с ними в точном виде, так как нас интересует только аппроксимированно-оптимальное решение. Мы используем параметр округления b (значение которого будет задано позднее) и будем рассматривать значения, округленные до целого, кратного b.

Алгоритм динамического программирования будет использоваться для решения задачи с округленными значениями. А точнее, для каждого элемента ∕ за его округленное значение принимается К К Обратите внимание: округленное и исходное значения достаточно близки друг к другу.

(11.34) Для каждого элемента выполняется v, < V, < v. + b.

Что нам дает округление? Если значения были изначально большими, то мень- ше они не станут. Однако все округленные значения представляют собой целые числа, кратные общему параметру b, поэтому вместо решения задачи с округлен- ными значениями v можно сменить «единицы измерения»; мы разделим все зна- чения на b и получим эквивалентную задачу Пусть v7∙ = vi ∕ b = [v. ∕ fe| для i = 1,..., п.

(11.35) Задача о рюкзаке со значениями и масштабированная версия задачи

■ч 0

со значениями имеют одинаковое множество оптимальных решении, оптималь- ные решения отличаются точно множителем b, а масштабированные значения являются целочисленными.

Теперь все готово к представлению аппроксимирующего алгоритма. Будем счи- тать, что все элементы имеют вес, не превышающий W (так как элементы с весом w > W заведомо не входят в решение и поэтому могут быть удалены). Также для простоты будем считать, что е-1 является целым числом.

Knapsack-Approx(e).·

Пусть b = (е/(2w)) mахлт

Решить задачу о рюкзаке со значениями ⅜ (эквивалентно V, ). Вернуть множество S найденных элементов

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

Еще по теме Разработка алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  12. Разработка Плана
  13. 2.7. Разработка анкеты
  14. 6. Разработка перспектив
  15. Разработка и принятие Основного закона
  16. Состояние научной разработки проблемы.
  17. Правило разработки веера версий
  18. Правило разработки графических схем
  19. Правило разработки графических схем
  20. Правило разработки веера версий