Примеры алгоритмов с ограниченным доступом

FF₁ — алгоритм FF с правилом 1.

FF₂ — алгоритм FF с правилом 2.

BF₁ — алгоритм BF с правилом 1.

BF₂ — алгоритм BF с правилом 2.

Теорема. Для любого K ³ 2

1) .

2) .

3) .

4) Для любого алгоритма A с ограниченным доступом к контейнерам

Алгоритм «Первый подходящий с упорядочиванием» (FFD)

· Сортируем предметы по невозрастанию весов
w ₁ ³ w ₂ ³ … ³ w_n

· Применяем алгоритм FF (BF).

Теорема. FFD (L) £ OPT (L) + 4 для всех L и существуют примеры со сколь угодно большими значениями OPT (L), для которых

FFD (L) ³ OPT (L).

Кроме того .

(Без доказательства)

Пример L = {1,…, 30 m }

6 m 3 m 6 m 2 m 3 m

OPT (L) = 9 m FFD (L) = 11 m