Задача об упаковке в контейнеры: различия между версиями

Теорема 1 [22]. R1FF = 17/10.

В дополнение к FF, еще пять простых эвристик были изучены в самом начале и послужили вдохновением для более поздних исследований. Best Fit (BF) – это вариант задачи FF, в котором каждый предмет помещается в контейнер, в который он может поместиться с наименьшим остатком свободного места; при наличии нескольких подходящих вариантов выбирается самый ранний из таких контейнеров. И FF, и BF могут быть реализованы за время O(n log n) [ ]. Next Fit (NF) – еще более простой алгоритм с линейным временем выполнения, в котором первый предмет помещается в первый контейнер, а каждый следующий предмет помещается в последний непустой контейнер, если он в него помещается, в противном случае открывается новый контейнер. First Fit Decreasing (FFD) и Best Fit Decreasing (BFD) – варианты этих алгоритмов, в которых входной список сначала сортируется по размеру в порядке неубывания, а затем применяется соответствующее правило упаковки. Для этих алгоритмов получены следующие результаты.

Theorem 2 [12]. R1NF = 2.

Теорема 4 [12, 13].