Минимизация цветов: вариант алгоритма рюкзака?

Мусорная упаковка или ранец?

Похоже, что эта проблема имеет больше общего с проблемой упаковки в мусорное ведро, чем с проблемой рюкзака. В задаче о рюкзаке вам нужно заполнить только один рюкзак, но его вместимость не должен превышать. И вы должны сделать это, максимизируя общую стоимость предметов, которые вы решите положить. Здесь вам не нужно использовать все предметы.

Однако в задаче об упаковке контейнеров у вас есть несколько контейнеров, каждый из которых имеет вместимость. Вы заинтересованы в минимизации количества корзин при размещении каждого элемента в какой-то корзине. Вы также должны соблюдать ограничение емкости каждого бункера. В отличие от ранца, здесь вы должны израсходовать все предметы.

В вашем случае вы также пытаетесь минимизировать количество бинов, только они не могут уместиться менее чем в два. И вы также хотите использовать все объекты. Вы немного сказали об ограничении емкости, но я предполагаю, что вы также должны уважать это. Пока это очень похоже на проблему упаковки в мусорное ведро. У вас также есть одно дополнительное ограничение: минимизировать количество цветов в каждом контейнере.

NP-жесткий?

Теперь я начинаю делиться с вами догадкой о том, что это NP-сложно — у него есть все элементы упаковки в мусорные ведра и одно дополнительное ограничение. Сокращение от бин-упаковки должно быть легко показано, скажем, с помощью экземпляра с объектами, окрашенными в красный цвет. Нам нужно только показать, что задача находится в NP, т. е. что мы можем проверить результат за полиномиальное время. Ну вот, у нас есть неофициальное доказательство!

Жадная эвристика I

Вот жадная эвристика, которая может помочь.

Представление: Вместо использования наборов рассмотрите последовательность битов длины k, где k — количество различных цветов, которые у вас есть. Итак, скажем, у вас есть 3 цвета — красный, зеленый, синий. Вы должны представить [синий] 001, [зеленый, синий] как 011, [красный] как 100 и т. д.

1. Отсортируйте элементы по последовательностям цветовых битов, используя функцию сравнения, которая приводит к такому порядку, как 001, 010, 100, 011, 110, 111. Вы можете разработать такую ​​функцию сравнения как взвешенную функцию Вес Хэмминга битовой последовательности и ее фактическое числовое значение.

2. Обратите внимание, что многие цветовые шаблоны (битовые последовательности), скорее всего, будут общими для многих объектов. Эти объекты будут отображаться как смежные объекты в отсортированном списке.

3. Перемещайтесь по отсортированному списку, назначая смежные элементы одного и того же цветового шаблона одному и тому же бункеру. Вы бы перешли от одноцветных к многоцветным предметам.

4. Продолжайте в том же духе, пока не исчерпаете вместимость каждой корзины.

Жадная эвристика II

Другим подходом было бы начать заполнение бункеров в обратном порядке. Начиная с объектов с наибольшим количеством цветов. Снова заполните смежные объекты в ту же корзину, если они могут поместиться. Когда вы доберетесь до предметов с меньшим количеством цветов, поместите их в существующие корзины, в которых уже есть этот цвет.

Вывод

Ни один из этих двух подходов не был бы оптимальным, но разве мы уже не знали об этом? Мы только что набросали неофициальное доказательство того, что задача является NP-сложной.

Удачи!