Определение частного случая подмножества с осложнениями
У меня есть проблема, о которой у меня есть ряд вопросов. Во-первых, я в основном ищу помощь в описании и понимании проблемы. Решения всегда приветствуются, но самое главное, я мог бы воспользоваться советом от кого-то более опытного, чем я. Теперь, к рассматриваемой проблеме:
У меня есть набор заказов, каждый из которых требует определенного количества предметов. У меня также есть несколько групп предметов, каждый из которых содержит некоторое количество некоторых предметов (назовите их группами). Цель состоит в том, чтобы найти подмножество заказов, которые могут быть выполнены с использованием как можно меньшего числа групп, и где общее количество элементов, содержащихся в заказах, находится между n и N.
Редактировать: ограничения на количество элементов, содержащихся в заказах (n и N), выбираются независимо.
По крайней мере, для меня это действительно сложный способ обозначить проблему, поэтому я пытался перефразировать ее как проблему ранца (я подозреваю, что это может привести к подмножеству суммы). Чтобы помочь моему концептуальному пониманию этого, я начал использовать следующие определения:
Во-первых, давайте предположим, что измерение существует для каждого возможного элемента, и что-то "длина" в этом измерении является номером того конкретного типа элемента, который у него есть или требуется.
Отсюда заказ становится "n-мерным объектом", где его значение в каждом измерении соответствует номеру этого элемента, который ему требуется.
Кроме того, группу можно рассматривать как "n-мерное поле", в котором в каждом измерении имеется пространство, соответствующее количеству элементов, которые она предоставляет.
Значение объекта равно сумме его длины во всех измерениях.
Коробки можно комбинировать.
Учитывая вышеизложенное, я перефразировал проблему следующим образом:
- Какая наименьшая комбинация блоков может содержать комбинацию элементов со значением между n и N.
Вопрос № 1: это правильный / полезный способ выразить проблему? Кажется, я что-то упустил очевидное?
На мой взгляд, поскольку я ищу две комбинации, мне нужно разбить проблему на две части. До сих пор я думаю, что решение этой проблемы - хороший шаг:
Сколько объектов может содержать бокс (или комбинация блоков) X?
Отметьте все (или, желательно, небольшое подмножество) возможных комбинаций ящиков и выберите "лучшие".
Это делает его немного более управляемым, но я все еще борюсь с деталями.
Вопрос № 2: Решено Для решения первой части, я думаю, уместно сказать, что стоимость объекта равна сумме его длины во всех измерениях, так же как и его стоимость. Это ставит меня в проблему с подмножеством, верно? Очевидно, это особый случай, но есть ли у этой проблемы имя?
Вопрос № 3: Решено Я много раз искал решения с подмножеством сумм, но не понимаю, как применить их к чему-то подобному в нескольких измерениях. Я предполагаю, что это было сделано раньше, но я не уверен, с чего начать свое исследование. Может ли кто-нибудь описать принципы работы или указать мне направление исследований?
Изменить: После просмотра отзывов каждого и поиска терминов, я думаю, что нашел хороший алгоритм, который я могу реализовать для решения части 1. Поскольку у меня будет очень большое количество измерений по сравнению с количеством элементов, которое выглядит как использование "Эвристическая первичная эффективная емкость ( PECH)" подойдет. Мне было бы интересно услышать, что кто-то думает об этом, если у них есть опыт работы с таким алгоритмом.
Вопрос № 4: Во второй части производительность - это проблема, и я сомневаюсь, что она будет реалистичной. Поэтому я намерен рассматривать все комбинации блоков как действительно большое дерево решений. Идея состоит в том, чтобы вычислить часть 1 для всех комбинаций блоков M-1, где M - общее количество блоков. Каким-то образом определите "лучшие" комбинации парных блоков из этого набора и сделайте то же самое с их дочерними узлами в дереве. Похоже ли это, что это поможет мне достичь чего-то близкого к оптимальному? Как бы я выбрал "лучшие" комбинации коробок?
Спасибо за прочтение! Предложения для редактирования и уточнения приветствуются.