FF1 — алгоритм FF с правилом 1.
FF2 — алгоритм FF с правилом 2.
BF1 — алгоритм BF с правилом 1.
BF2 — алгоритм BF с правилом 2.
Теорема. Для любого K ³ 2
1) .
2) .
3) .
4) Для любого алгоритма A с ограниченным доступом к контейнерам
Алгоритм «Первый подходящий с упорядочиванием» (FFD)
· Сортируем предметы по невозрастанию весов
w 1 ³ w 2 ³ … ³ wn
· Применяем алгоритм 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