4551
правка
Задача об упаковке в контейнеры: различия между версиями
Перейти к навигации
Перейти к поиску
м
Задача об упаковке в контейнеры (посмотреть исходный код)
Версия от 20:31, 21 января 2024
, 21 январь→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Задача раскроя == Постановка задачи == В одномерной задаче упаковки контейнеров на входе имеется список L = (a1; a2... ; an) предметов; каждый предмет ai имеет размер s(ai) 2 (0, 1]. Задача состоит в том, чтобы упаковать предметы в минималь...») |
Irina (обсуждение | вклад) Метка: визуальный редактор отключён |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
В одномерной задаче упаковки контейнеров на входе имеется список L = ( | В одномерной задаче упаковки контейнеров (bin packing) на входе имеется список <math>L = (a_1, a_2, ..., a_n)</math> предметов; каждый предмет <math>a_i</math> имеет размер <math>s(a_i) \in (0, 1]</math>. Задача состоит в том, чтобы упаковать предметы в минимальное число контейнеров единичной емкости, то есть разбить предметы на минимальное число наборов, каждый из которых имеет общий размер не более 1. Эта задача является NP-трудной, поэтому большая часть исследований по ней связана с разработкой и анализом аппроксимационных алгоритмов, которые и станут темой данной статьи. | ||