Жадный алгоритм в задачах о покрытии/Задачи/fist-fit-for-vector-packing — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена :Решенные задачи на :Нерешенные задачи) |
StasFomin (обсуждение | вклад) (Массовая правка: добавление Категория:Теоретические задачи) |
||
(не показана одна промежуточная версия этого же участника) | |||
Строка 9: | Строка 9: | ||
найдет (d+1)-оптимальное решение. | найдет (d+1)-оптимальное решение. | ||
− | [[Категория: | + | [[Категория:Решенные задачи]] |
+ | [[Категория:Теоретические задачи]] |
Текущая версия на 06:50, 4 мая 2023
Рассмотрим многомерное обобщение задачи Упаковки в контейнеры, называемое Vector Packing.
Там размеры всех предметов → d-мерный вектор, контейнеры тоже d-мерный вектора (V,…,V), и цель — упаковать все предметы в минимум контейнеров, так, чтобы упакованные в контейнеро предметы, после векторного суммирования[1], не вылезали за его границы.
Покажите, что приближенный алгоритм, типа First Fit, обобщенный для многомерности,
найдет (d+1)-оптимальное решение.- ↑ Т.е. это не как упаковка в многомерном тетрисе