Алгоритмы задач об упаковке в контейнеры: Следующий подходящий (NF), Первый подходящий (FF), Наилучший подходящий (BF), On-line, с ограниченным доступом к контейнерам, первый подходящий с упорядочиванием (FFD). Релаксация линейного программирования.
В теории сложности вычислений 0 такое, что RA (L) ≤ r для всех L с OPT(L) ≥ N}. 1.2. Алгоритм «Первый подходящий» (FF) В произвольном порядке упаковываем предметы по следующему правилу. На k-м шаге находим контейнер с наименьшим номером, куда помещается k-й предмет, и помещаем его туда. Т = О(n2), П = О(n). Теорема. для всех L и существуют примеры со сколь угодно большими значениями OPT, для которых (Без доказательства). Пример. 1.3.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
