4430
правок
Аппроксимационные схемы для задачи об упаковке в контейнеры: различия между версиями
Материал из WEGA
Аппроксимационные схемы для задачи об упаковке в контейнеры (посмотреть исходный код)
Версия от 17:34, 12 марта 2024
, 12 март→Нотация
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Задача раскроя == Постановка задачи == В задаче об упаковке в контейнеры входными данными является набор предметов, определяемых их размерами. Также имеются одинаковые контейнеры, размеры...») |
Irina (обсуждение | вклад) м (→Нотация) |
||
| Строка 11: | Строка 11: | ||
== Нотация == | == Нотация == | ||
Исходными данными для задачи упаковки в контейнеры является набор I из n предметов, заданных их размерами | Исходными данными для задачи упаковки в контейнеры является набор <math>I</math> из n предметов, заданных их размерами <math>s_1, ..., s_n</math>, где каждый размер <math>s_i</math> представляет собой вещественное число в диапазоне (0, 1]. Подмножество предметов <math>S \subseteq I</math> может быть упаковано в контейнер, если общий размер предметов в S не превышает 1. Задача заключается в том, чтобы упаковать все предметы из I в минимальное количество контейнеров. Обозначим за OPT(I) значение оптимального решения, а за Size(I) – общий размер всех предметов в I. Очевидно, что <math>OPT(I) \ge \lceil Size(I) \rceil</math>. | ||
| Строка 17: | Строка 17: | ||
Алгоритм называется асимптотической | Алгоритм называется асимптотической <math>\rho</math>-аппроксимацией, если требующееся ему количество контейнеров равно <math> \rho \cdot OPT(I) + O(1)</math>. | ||
== Основные результаты == | == Основные результаты == | ||
