Вопрос динамического программирования бин-упаковки

Ответ 1

Это не глупый вопрос, ИМО.

Известно, что упаковка в банке NP-Complete.

Но ваш случай, упаковка бина с фиксированным количеством весов объектов является интересным вариантом.

В следующей статье утверждается, что алгоритм полиномиального времени имеет 1 оптимальный: http://linkinghub.elsevier.com/retrieve/pii/S0377221706004310, когда вы разрешаете 3 разных размера. (Предостережение: я только иду абстрактным).

Итак, я предполагаю, что эта версия тоже NP-Hard, и алгоритм Greedy, скорее всего, не сработает. Не так уверен в динамическом программировании (упаковка в банке сильно NP-Complete).

Надеюсь, что это поможет.

Ответ 2

Это не будет эффективно, но вы можете решить эту <забастовку > в полиномиальное время с помощью простого алгоритма динамического программирования. Степень полинома будет зависеть от количества различных размеров, которые у вас есть.

Я включил реализацию, которая для 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

Ответ 3

Это можно сделать в 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]

Ответ 4

Если вы можете уменьшить свою проблему до 1-й бин-упаковки, вы хотите использовать жадный алгоритм, используемый здесь: http://www.developerfusion.com/article/5540/bin-packing

Ответ 5

Если размер является одномерным, или если его можно свести к одномерному значению, вы можете решить эту проблему как проблему с несколькими мешками (MKP), где вес элемента равен его выгоде. Если вы установите #bin на верхнюю границу для количества доступных элементов (одним взглядом, если ваш экземпляр не очень высок, это значение может быть #items), вы можете решить эту проблему оптимально с помощью ветки и привязки или другой алгоритм оптимизации. Если вы можете принять неоптимальное решение, есть некоторые возможные жадные алгоритмы.

Однако я не уверен, потому что я никогда не изучал эту проблему глубоко. Тем не менее, есть книга под названием "Проблемы с рюкзаками", в которой представлены формулировки и алгоритмы, в том числе проблемы упаковки упаковки. Не трудно найти его как PDF в Интернете.

Надеюсь на эту помощь. Удачи.

Ответ 6

Минимальное количество ящиков, предполагающих отличную упаковку, будет B = ceiling( sum(n(i)*s(i) for i in 1..3) / C )

Используйте то, что называется first_fit, но на самом деле худший_fit, с заменой, здесь, чтобы узнать, вписываются ли элементы в ячейки B. Если нет, добавьте B и повторите, пока они не подойдут.

Ответ 7

Здесь представлен эскиз алгоритма 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).

Ответ 8

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

Предположим, что элементы размера 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).