У вас есть n1 элементов размера s1, n2 элементов размера s2 и n3 элементов размера s3. Вы хотите упаковать все эти элементы в ячейки каждой емкости C, чтобы общее количество использованных ящиков было сведено к минимуму.
Как мы можем достичь решения, используя минимальное количество ящиков? Жадность не работает.
Это не глупый вопрос, ИМО.
Известно, что упаковка в банке NP-Complete.
Но ваш случай, упаковка бина с фиксированным количеством весов объектов является интересным вариантом.
В следующей статье утверждается, что алгоритм полиномиального времени имеет 1 оптимальный: http://linkinghub.elsevier.com/retrieve/pii/S0377221706004310, когда вы разрешаете 3 разных размера. (Предостережение: я только иду абстрактным).
Итак, я предполагаю, что эта версия тоже NP-Hard, и алгоритм Greedy, скорее всего, не сработает. Не так уверен в динамическом программировании (упаковка в банке сильно NP-Complete).
Надеюсь, что это поможет.
Это не будет эффективно, но вы можете решить эту <забастовку > в полиномиальное время с помощью простого алгоритма динамического программирования. Степень полинома будет зависеть от количества различных размеров, которые у вас есть.
Я включил реализацию, которая для 3 разных размеров будет O(n1 * n2 * n3 * (C/s2) * (C/s3) * ((n1*s1 + n2*s2 + n3*s3)/C)) с довольно дрянной константой. (Эта цифра объясняется тем фактом, что мы имеем число различных моделей доступности O(n1 * n2 * n3), и для каждого из них мы генерируем O((C/s2) * (C/s3)) возможные следующие бункеры, для каждого из которых мы должны работать с набором ящиков, чьи размер O((n1*s1 + n2*s2 + n3*s3)/C)). Ряд рутинных оптимизаций может значительно ускорить эту программу.)
#! /usr/bin/python
import heapq
def min_bins(bin_size, sizes, counts):
available = zip(sizes, counts)
available.sort(reverse=True)
seen = set([])
upcoming = [(0, available, [])]
while 0 < len(upcoming):
(n, available, bins) = heapq.heappop(upcoming)
for (bin, left) in bin_packing_and_left(bin_size, available):
new_bins = bins + [bin]
if 0 == len(left):
return new_bins
elif left not in seen:
heapq.heappush(upcoming, (n+1, left, new_bins))
seen.add(left)
def bin_packing_and_left(bin_size, available, top=True):
if 0 == len(available):
yield ((), ())
else:
(size, count) = available[0]
available = available[1:]
for (bin, left, used) in bin_packing_and_left_size(bin_size, available):
can_use = (bin_size - used) / size
if count <= can_use:
yield(((size, count),) + bin, left)
elif 0 < can_use:
yield(((size, can_use),) + bin,
((size, count - can_use),) + left)
else:
yield(bin, ((size, count),) + left)
def bin_packing_and_left_size(bin_size, available):
if 0 == len(available):
yield ((), (), 0)
else:
(size, count) = available[0]
available = available[1:]
for (bin, left, used) in bin_packing_and_left_size(bin_size, available):
for i in range(1 + min(count, (bin_size - used) / size)):
if count == i:
yield(((size, count),) + bin, left, used + size * count)
elif 0 < i:
yield(((size, i),) + bin,
((size, count - i),) + left,
used + size * i)
else:
yield(bin, ((size, count),) + left, used)
answer = min_bins(23, (2, 3, 5), (20, 30, 40))
print len(answer)
print answer
Это можно сделать в O(n1*n2*n3)...
Допустим, что f(i,j,k) - минимальное значение no. которые должны соответствовать i, j и k элементам размера s1, s2, s3 соответственно.
Примечание: C - емкость ячейки
f(i,j,k) будет содержать 2 вида информации:
a) (The min no. of bins that are currently required) - 1. Скажем, что свойство B1.
b) Текущий размер последнего бина, который доступен для дальнейшей подачи. Скажем, свойство B2.. где 0 < B2 <= C
Следовательно, повторение будет:
f(i,j,k)([B1],[B2]) =
min
{
f(i-1, j, k)( [B1] + [B2 + S1]/(C+1) , [B2 + S1] <=C ? [B2 + S1] : [B2 + S1 - C]) ,
f(i, j-1, k)( [B1] + [B2 + S2]/(C+1) , [B2 + S2] <=C ? [B2 + S2] : [B2 + S2 - C]) ,
f(i, j, k-1)( [B1] + [B2 + S3]/(C+1) , [B2 + S3] <=C ? [B2 + S3] : [B2 + S3 - C])
}
Минимальный номер. требуемых бункеров: 1 + f(n1, n2, n3)[B1]
Если вы можете уменьшить свою проблему до 1-й бин-упаковки, вы хотите использовать жадный алгоритм, используемый здесь: http://www.developerfusion.com/article/5540/bin-packing
Если размер является одномерным, или если его можно свести к одномерному значению, вы можете решить эту проблему как проблему с несколькими мешками (MKP), где вес элемента равен его выгоде. Если вы установите #bin на верхнюю границу для количества доступных элементов (одним взглядом, если ваш экземпляр не очень высок, это значение может быть #items), вы можете решить эту проблему оптимально с помощью ветки и привязки или другой алгоритм оптимизации. Если вы можете принять неоптимальное решение, есть некоторые возможные жадные алгоритмы.
Однако я не уверен, потому что я никогда не изучал эту проблему глубоко. Тем не менее, есть книга под названием "Проблемы с рюкзаками", в которой представлены формулировки и алгоритмы, в том числе проблемы упаковки упаковки. Не трудно найти его как PDF в Интернете.
Надеюсь на эту помощь. Удачи.
Минимальное количество ящиков, предполагающих отличную упаковку, будет B = ceiling( sum(n(i)*s(i) for i in 1..3) / C )
Используйте то, что называется first_fit, но на самом деле худший_fit, с заменой, здесь, чтобы узнать, вписываются ли элементы в ячейки B. Если нет, добавьте B и повторите, пока они не подойдут.
Здесь представлен эскиз алгоритма DP для этого.
Рекурсивное отношение: мы возвращаем на B(i, j, k) минимальное количество ящиков емкости C, необходимых для упаковки я элементов размера s1, j элементов размера s2 и k элементов размера s3. Отношение:
B(i, j, k) = min {B (x,y,z) , B(i-x, j-y, k-z)}
where 0<=x<=i;
0<=y<=j;
0<=z<=k
где по крайней мере один из x, y или z должен быть больше, чем 0, а один из x, y или z должен быть меньше i, j или k соответственно.
Время выполнения: B - размер O (n3), и для вычисления каждого элемента B требуется время O (n3) для общего времени O (n6).
Если мы сможем найти оптимальное решение для одного бина, это означает, что максимальное количество элементов, которые я могу поместить в один бит, приведет к ответу.
Предположим, что элементы размера S1, b элементов размера S2, c элементов размера S3 - это максимальное количество элементов, которые я могу поместить в один бит. Таким образом, максимальный размер, который я могу поместить в один бит, равен K = a * S1 + b * S2 + c * S3.так, ответ будет (n1 * S1 + n2 * s2 + n3 * s3)/K + (n1 * S1 + n2 * s2 + n3 * s3)% K no из бункеров.
Найти K проще, чем стандартная проблема Knapsack. Если я предполагаю, что все оптимальные значения до я существуют 1 <= я <= C. Тогда оптимальное значение я + 1 может быть записано рекурсивно как
M(i+1) = max(M(i),M(i-S1)+S1,M(i-S2)+S2,M(i-S3)+S3).