Улучшенное решение

Все это наводит на мысль, что решение потребует больше подзадач: для определе- ния значения OPT(n) необходимо знать не только значение OPT(n - 1), но и лучшее


решение, которое может быть получено с использованием подмножества первых n - 1 элементов и общего доступного веса W - wn.
А следовательно, подзадач будет намного больше: по одной для каждого исходного множества {1, ..., i} элементов и для каждого возможного значения оставшегося доступного веса w. Предположим, W — целое число, а все запросы i = 1, ..., n имеют целые веса w. Тогда подзадача соз- дается для каждого i = 0,1, ..., n и каждого целого числа 0 < w < W. Для оптимального решения, использующего подмножество элементов {1,..., i} с максимально допусти- мым весом w, будет использоваться решение OPT(i, w), то есть

где максимумопределяется по подмножествам S !Ξ {1, ..., i}, удовлетворяющим ус- ловиюС этим новым множеством подзадач мы сможем представить

значение OPT(i, w) в виде простого выражения, использующего значения меньших подзадач. Более того, OPT(n, W) — значение, которое мы ищем в конечном итоге. Как и прежде, пусть O обозначает оптимальное решение исходной задачи.

♦ Если n ⅜ O, то OPT(n, W) = OPT(n - 1, W), так как элемент n можно просто игно- рировать.

♦ Если n O, то OPT(n, W) = wn + OPT(n - 1, W- wn), так как теперь ищется вариант оптимального использования оставшейся емкости W - wn между элемента- ми 1, 2, ..., n - 1.

Когда n-й элемент слишком велик, то есть W < wn, должно выполняться условие OPT(n, W) = OPT(n - 1, W). В противном случае мы получаем оптимальное решение, допускающее все n заявок, выбирая лучший из этих двух вариантов. Применяя аналогичные рассуждения для подзадачи с элементами {1, ..., i} и максимальным допустимым весом w, получаем следующее рекуррентное отношение:

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

Как и прежде, мы хотим создать алгоритм, который строит таблицу всех значе- ний OPT(i, w), вычисляя каждое из них не более одного раза.

Subset-Sum (n, W)

Массив M[0...n,0...W]

Инициализировать M[0, w] = 0 для всех w = 0,1..................... W

For i = 1,2.............. n

For w = 0............. W

Использовать рекуррентное отношение (6.8) для вычисления M\_i,w~\

Конец For Конец For Вернуть M[n, W\

При помощи (6.8) можно немедленно доказать посредством индукции, что возвращаемое значение M[ n, W] является значением оптимального решения для заявок 1, ..., n и доступного веса W.

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

Еще по теме Улучшенное решение:

  1. Статья 778. Улучшение нанимателем вещи, переданной в найм
  2. 3. Права и обязанности сторон в связи с улучшением арендованного имущества.
  3. 5.2.12. Укрепление и улучшение места (или мест), придающего уверенность
  4. Психологические аспекты улучшения работы по профилактике дорожно-транспортных нарушений.
  5. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  6. РЕШЕНИЕ
  7. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  8. ПРИНЯТИЕ РЕШЕНИЙ
  9. РЕШЕНИЯ КСУ
  10. Не избегайте принятия решений
  11. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ