Здравствуйте!
Я занимаюсь задачей упаковки в контейнеры. Если быть точнее, я пытаюсь оценить нижнюю границу на количество контейнеров необходимых при "частичной доупаковке", то есть когда есть какое-то начальное решение и нам надо доупаковать оставшиеся предметы, минимизируя количество контейнеров. В целом, как искать нижнюю границу "полной упаковки" хорошо известно - с помощью генерации столбцов. Но, т.к. при частичной доупаковке теряется одинаковый размер контейнеров - это слегка проблематично.
Кроме прочего у меня чуть больше ограничений, чем в обычной задаче. К примеру ограничения не на один ресурс, а на два, конфликты и т.д., не буду вдаваться в подробности.
Я разработал некоторый алгоритм, который оценивает нижнюю границу и он даже иногда дает результат лучше, чем нижняя граница "полной упаковки".
Наконец, перейдем к моему вопросу. Мне кажется я могу сильно улучшить этот алгоритм и это улучшение сильно связано с задачей ниже:
Пусть даны

- матрица

, причем

. И число

. Обозначим класс множеств

.
Необходимо найти, такие

, что

.
То есть линейное диофантово уравнение над положительными натуральными числами

, должно раскладываться на две подзадачи

,

, что сумма множеств решений этих подзадач в точности равняется множеству решений первой задачи.
Такие разложения есть и на самом деле они не так редки. Естественно, можно просто найти это "перебором", с помощью солверов целочисленного программирования, но боюсь, что это будет достаточно долго считаться и не всегда такое разложение будет существовать. Кроме этого, я не до конца разобрался, возможно стоит рассматривать не равенство, а неравенство

, где

- первый столбец матрицы

(считаем, что в каждой строке элементы отсортированы), так или иначе решение первой задачи наверняка что-то скажет о второй. В идеале, если получится искать разложения не зная внутренней структуры множеств

.
Кроме этого, задачу можно сформулировать и так: Найти такой

. Где

.
Буду благодарен, если поделитесь своими мыслями по этой задаче!