Проблема упаковки - PullRequest
Новая
       3

Проблема упаковки

0 голосов
/ 04 марта 2011

У меня следующая проблема:

  1. У меня есть заданное количество одинаково сформированных предметов с разными цветами (я знаю, сколько их у каждого цвета)
  2. Я упаковываю ихэлементы в ящики, которые могут содержать каждое заданное количество (n) предметов таким образом, чтобы я использовал минимальное количество ящиков: round_up (total_nr_of_items / n)
  3. Есть некоторые цвета, которые мне не разрешено помещать водна коробка, если только у меня не будет идеального количества коробок.
  4. Существует минимальное количество предметов каждого цвета (разных для каждого цвета), которые я могу положить в коробку.То есть я могу решить поставить 0 шт.одного цвета в коробку или минимум k шт.или выше.Это ограничение также может быть нарушено (как можно меньше раз), если упаковка не может быть выполнена с минимальным количеством коробок.
  5. Я хочу найти решение, в котором как можно меньше цветов разделено на квадраты.

Я думаю, что это своего рода проблема с упаковкой, но я не знаю, какой именно.

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

Ответы [ 2 ]

3 голосов
/ 07 марта 2011

Похоже, NP-Hard проблема удовлетворения ограничений .У вас будут жесткие и мягкие ограничения, подобные следующим.

Встроенные ограничения:

  • У меня есть заданное количество одинаково сформированных предметов с разными цветами (я знаю, сколько их там* из каждого цвета)

Жесткие ограничения:

  • Есть несколько цветов, которые я не могу поместить в один ящик.

  • Существует минимальное количество предметов каждого цвета (разных для каждого цвета), которые я могу положить в коробку.То есть я могу решить поставить 0 шт.одного цвета в коробку или минимум k шт.или выше.

Мягкие ограничения:

  • Я упаковываю эти предметы в коробки, в которых можно хранить каждый номер (n) предмета таким образом, чтобы я использовал минимумколичество ящиков: round_up (total_nr_of_items / n)

Более мягкие ограничения (или мягкие ограничения с очень небольшим весом):

  • Я хочу найти решение, в котором как можно меньше цветовВозможные варианты делятся на блоки.

Для алгоритмов решения этой проблемы взгляните на Имитация отжига , Поиск по Табу , Ветвление и граница , ...

Для программного обеспечения, которое реализует такие алгоритмы и поддерживает ограничения, взгляните на Drools Planner (Java, открытый исходный код).

1 голос
/ 04 марта 2011

Это может быть NP-Hard.

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

Учитывая массив натуральных чисел A [1, ... n], из которых нам нужно найти некоторое подмножество, имеет ту же сумму, что и его дополнение.

Считайте, что ваши цвета от 1 до n. У вас есть две коробки. минимум, который коробка может содержать для цвета i, равен A [i], и у вас есть ровно A [i] элементы цвета i.

Максимальное количество предметов, которое может вместить каждый ящик: (A [1] + .. + A [n]) / 2.

...