combinations of sizes for shipping

Question

Hi there, I've got a bunch of products with sizes to ship and I need to find out the cheapest rate.

Given a shipment made out of sizes, say [1,3,3,5] I need to decide how to ship - all together or separate. However it's not as simple as [1,3,3,5] or 1 & 3 & 3 & 5, i need all of the possible combinations something like:

[
[[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 )
]

( etc - many more i assume ) I've tried combinations from the facets gem but it's not quite what i'm after, and I'm not sure how else to approach this problem. I understand it probably has a name and a solution if only I knew the name :)

I understand there could be a lot of combinations, but the initial array of sizes won't be larger than 7 or so.

Thanks in advance!

Answer 1

Maybe a look here http://en.wikipedia.org/wiki/Packing_problem and here http://en.wikipedia.org/wiki/Knapsack_problem could be inspiring...

Answer 2

For N <= 7, you can simply be exhaustive:

In C-ish pseudo-code with bitmask:

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 )

where "append i to current" means getting the indices, putting it in a list and appending it. If you want to play with optimization, you can even memoize it.

Answer 3

I guess you want to generate the partitions of a set.

Here is very good explanation and working code to do it.

But doing this is not a very good idea as it leads to Combinatorial Explotion.

There are such things for n.

I think you have a knapsack problem and dynamic programming is the right way to solve it.

Answer 4

This problem is known as the Variable-Sized Bin Packing Problem in the combinatorial optimization literature. Since it generalizes Bin Packing, it's NP-hard, but techniques like branch and bound should do a reasonable job on instances too large to be handled by brute force.