Предположим, что есть n элементов и бункеров, и каждый лоток имеет размер s.Упорядочение добавленных вами ограничений на самом деле значительно упрощает проблему.
Они конкретно означают, что мы всегда должны выбирать элементы 1, 2, ..., m для наибольшего m <= n, которое будет соответствоватьвыделенное количество ячеек (поскольку выбор меньшего числа обязательно приведет к худшему решению по правилу 1).Элементы будут упакованы в контейнеры в этом порядке, возможно, с некоторыми контейнерами, оставленными не полностью заполненными (поскольку перестановка элементов внутри корзины или между контейнерами может привести к худшему решению по правилу 2).Есть 2 случая: </p>
- m
- m = n, и в этом случае мы можем разместить все элементы.Теперь рассмотрим подслучаи этого случая.
В этом случае может оказаться возможным, что плотно упакованные контейнеры оставят окончательный блок 0
Теперь мы точно знаем, какие элементы и какие корзины мы будем использовать.Мы также знаем порядок, в котором товары должны быть упакованы.Из-за ограничения порядка мы можем рассматривать решения о том, какие ячейки следует оставить не полностью заполненными, как проблему о том, как вводить инструкции «start-next-bin» в упорядоченный список 1, 2, ... nиз предметов .Мы можем ввести до r-1 этих инструкций.
Эта проблема может быть решена за O (nrs) время с помощью динамического программирования.По сути, мы вычисляем функцию:
f (i, j, k) = оценка наилучшего решения, в котором первые элементы i занимают первые j блоков, причем ровно k элементов в j-м блоке.
Повторение:
f(i, j, 0) = max(f(i, j-1, k)) over all 0 <= k <= s
f(i, j, k > 0) = f(i-1, j, k-1) + q(i, j)
Где q (i, j) - показатель качества присвоения элемента i блоку j.(Как я уже упоминал в комментариях к вашему сообщению, вам нужно решить, каким образом можно назначить оценки для размещения любого элемента i в любом блоке j, предположительно, исходя из того, насколько хорошо выполнены мои предпочтения. Если с ним легче работать »значения «плохое», чем значения качества, просто измените max() на min() и -infinity граничные значения ниже на infinity.)
Первое уравнение говорит, что лучший результат решения дляпервые элементы i, у которых крайняя правая корзина пуста, равны наилучшей оценке, которую можно найти, рассматривая каждое решение для первых элементов i без этой корзины.Эти подходящие решения состоят из всех способов, которыми может быть упакован предыдущий контейнер, в том числе и оставляя его пустым.
Второе уравнение говорит о том, что лучший результат для первых элементов i, чей крайний правый контейнер не пуст, находится простодобавив показатель качества для размещения последнего элемента к лучшему результату для размещения первых элементов i-1 в том же количестве ячеек.
Граничные условия:
f(0, 0, 0) = 0
f(i, 0, k) = -infinity for all other i and k
Послевычисление значений f (i, j, k) для каждого 0 <= i <= n, 0 <= j <= r и 0 <= k <= s и сохранение их в таблице f (n, r,s) даст оптимальную оценку окончательного решения.Хотя это дает только оценку максимума, фактическое оптимальное решение (я) можно найти, проследив обратно через матрицу f (i, j, k) с конца, на каждом шаге k = 0 в поиске состояния предшественника (то есть альтернатива под <code>max()), которая должна была привести к текущему состоянию.(Может случиться, что несколько альтернатив под max() дают равные оценки, и в этом случае существует несколько оптимальных решений, и любой из этих путей может быть найден, чтобы найти только один из них.)