> Перший предмет поміщаємо в першу контейнер.
На k-му кроці знаходимо контейнер з найменшим номером, куди поміщається k-й предмет, і поміщаємо його туди. Якщо такого контейнера немає, то беремо новий
порожній контейнер і поміщаємо предмет в нього. Т=О (n2), П=О (n).
Теорема. для всіх L і існують приклади з як завгодно великими значеннями OPT, для яких
(Без доведення).
Приклад.
1.3. Алгоритм «Найкращий відповідний» (BF)
У довільному порядку пакуємо предмети за наступним правилом.
Перший предмет поміщаємо в першу контейнер.
На k-му кроці розміщуємо k-й предмет. Знаходимо частково заповнені контейнери, де досить для нього вільного місця і вибираємо серед них найбільш заповнений. Якщо таких немає, то беремо новий порожній контейнер і поміщаємо k-й предмет в нього. Т=О (n2), П=О (n).
Теорема.
і існують приклади з як завгодно великими значеннями OPT (L), для яких BF (L)=4/3 FF (L) і FF (L)=3/2 BF (L).
.4. Алгоритми типу On-line
Предмети надходять в непередбачуваному порядку. Требуется упакувати їх в мінімальне число контейнерів. Упакований предмет не можна переміщати в інший контейнер. Місце для попереднього зберігання предметів відсутня.
Алгоритми NF, FF, BF є On-line алгоритмами.
Теорема. Для будь-якого On-line алгоритму A справедливо нерівність
(Без доведення).
1.5. Алгоритми з обмеженим доступом до контейнерів
line алгоритм називають алгоритмом з обмеженим доступом до контейнерів, якщо на кожному кроці алгоритм має можливість поміщати предмети тільки в один з K контейнерів (K - const). Ці контейнери називаються відкритими. Якщо контейнер закрили, то він вже не відкривається (наприклад, відправляється споживачу). Перш ніж додати порожній відкритий контейнер, потрібно закрити один з K відкритих контейнерів.
Алгоритм NF - приклад для K=1.
Правила для вибору контейнера:
. Закрити контейнер з найменшим номером
. Закрити самий заповнений контейнер.
Приклади алгоритмів з обмеженим доступом-алгоритм FF з правилом 1. - алгоритм FF з правилом 2. - алгоритм BF з правилом 1. - алгоритм BF з правилом 2.
Теорема. Для будь-якого K? 2
.6. Алгоритм «Перший підходящий з впорядкуванням» (FFD)
Сортуємо предмети за незростання ваг w1? w2? ...? wn
Застосовуємо алгоритм FF (BF).
Теорема.
для всіх L і існують приклади з як завгодно великими значеннями OPT (L), для яких
Крім того
(Без доведення).
Приклад
Асимптотичні гарантовані оцінки точності
Теорема. Для будь...
