Просмотр исходного текста страницы Жадный алгоритм в задачах о покрытии/Задачи/fist-fit-for-vector-packing

<!-- cabook-ex-02-11-p98 -->
Рассмотрим многомерное обобщение задачи [https://en.wikipedia.org/wiki/Bin_packing_problem Упаковки в контейнеры], называемое Vector Packing.

Там размеры всех предметов → d-мерный вектор, 
контейнеры тоже d-мерный вектора (V,…,V), и цель — упаковать все предметы в минимум контейнеров, 
так, чтобы упакованные в контейнеро предметы, после векторного суммирования<ref>Т.е. это не как упаковка в многомерном тетрисе</ref>, не вылезали за его границы.

Покажите, что приближенный алгоритм, типа [https://en.wikipedia.org/wiki/Bin_packing_problem First Fit], обобщенный для многомерности,
найдет (d+1)-оптимальное решение.

[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]