4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Нотация) |
||
Строка 11: | Строка 11: | ||
== Нотация == | == Нотация == | ||
Исходными данными для задачи упаковки в контейнеры является набор <math>I</math> из n предметов, заданных их размерами <math>s_1, ..., s_n</math>, где каждый размер <math>s_i</math> представляет собой вещественное число в диапазоне (0, 1]. Подмножество предметов <math>S \subseteq I</math> может быть упаковано в контейнер, если | Исходными данными для задачи упаковки в контейнеры является набор <math>I</math> из n предметов, заданных их размерами <math>s_1, ..., s_n</math>, где каждый размер <math>s_i</math> представляет собой вещественное число в диапазоне (0, 1]. Подмножество предметов <math>S \subseteq I</math> может быть упаковано в контейнер, если суммарный размер предметов в S не превышает 1. Задача заключается в том, чтобы упаковать все предметы из <math>I</math> в минимальное количество контейнеров. Обозначим за OPT(I) величину оптимального решения, а за Size(I) – общий размер всех предметов в <math>I</math>. Очевидно, что <math>OPT(I) \ge \lceil Size(I) \rceil</math>. | ||
Строго говоря, для этой задачи не допускается наличие алгоритма полиномиального времени с гарантией аппроксимации лучше 3/2. Любопытно, однако, что это не исключает существования алгоритма, требующего, скажем, OPT(I) + 1 контейнеров (в отличие от других задач оптимизации, в случае упаковки в контейнеры создание нескольких копий маленького «сложного экземпляра задачи» для получения сложного экземпляра величины не работает). Более осмысленно рассматривать гарантии аппроксимации в асимптотическом смысле. | Строго говоря, для этой задачи не допускается наличие алгоритма полиномиального времени с гарантией аппроксимации лучше 3/2. Любопытно, однако, что это не исключает существования алгоритма, требующего, скажем, OPT(I) + 1 контейнеров (в отличие от других задач оптимизации, в случае упаковки в контейнеры создание нескольких копий маленького «сложного экземпляра задачи» для получения сложного экземпляра большей величины не работает). Более осмысленно рассматривать гарантии аппроксимации в асимптотическом смысле. | ||
правок