комбинации размеров для доставки

Question

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

Учитывая груз, сделанный из размеров, скажем, [1,3,3,5] Мне нужно решить, как отправить - все вместе или отдельно. Однако это не так просто, как [1,3,3,5] или 1 & 3 & 3 & 5, мне нужны все возможные комбинации, например:

[
[[1,3,3,5]],           ( 1 shipment )
[[1],[3,3,5]],         ( 2 shipments )
[[1,3],[3,5]],         ( 2 shipments )
[[1,3,3],[5]],         ( 2 shipments )
[[1,5],[3,3]],         ( 2 shipments ) 
[[1,3],[3],[5]],       ( 3 shipments )
[[1],[3],[3],[5]]      ( 4 shipments )
]

(и т. Д., Я полагаю, еще много) Я пробовал комбинации из драгоценного камня Facets, но это не совсем то, к чему я стремлюсь, и я не уверен, как еще подойти к этой проблеме. Я понимаю, что, вероятно, у него есть имя и решение, если бы я только знал это имя:)

Я понимаю, что комбинаций может быть много, но исходный массив размеров не будет больше 7 или около того.

Заранее спасибо!

Answer 1

Я думаю, вы хотите сгенерировать разделов набора .

Вот очень хорошее объяснение и рабочий код для этого.

Но делать это не очень хорошая идея, поскольку это приводит к Комбинаторному исследованию .

Есть таких вещей для n.

Я думаю, у вас проблема с рюкзаком и динамическое программирование - верный способ ее решения.

Answer 2

Для N <= 7 вы можете просто быть исчерпывающим:

В псевдокоде C-ish с битовой маской:

result = ()
subsets( int x, list current )
    if ( x == 0 )
        result.append( current )

    for ( int i = x; i >= 0; i = ( ( i - 1 ) & x ) )
        subsets( x ^ i, append i to current )

где «добавить i к текущему» означает получение индексов, помещение их в список и добавление их. Если вы хотите поиграть с оптимизацией, вы даже можете запомнить ее.

Answer 3

Может быть, взгляд здесь http://en.wikipedia.org/wiki/Packing_problem и здесь http://en.wikipedia.org/wiki/Knapsack_problem может быть вдохновляющим ...

Answer 4

Эта проблема известна в литературе по комбинаторной оптимизации как проблема упаковки бункеров с переменным размером. Так как он обобщает Bin Packing, он сложен с точки зрения NP, но такие методы, как ветвление и связывание, должны выполнять разумную работу в случаях, когда они слишком велики для обработки грубой силой.