Combinations of sizes for delivery
I have a bunch of sized products to ship and need to find out the cheapest rate.
Given that the cargo is made of dimensions, say [1,3,3,5], I need to decide how to ship - all together or separately. However, it is not as easy as [1,3,3,5] or 1 and 3 and 3 and 5, I need all possible combinations:
[
[[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 others, I suppose) I've tried combinations of gem facets, but that's not exactly what I need and I'm not sure how else to approach this problem. I realize that it probably has a name and a solution, if only I knew the name :)
I understand there can be many combinations, but the initial size array will not be larger than 7 or so.
Thanks in advance!
a source to share
I think you want to generate the set sections .
Here is a very good explanation and working code for this.
But doing this is not very good, as it leads to Combinatorial Explotion .
There are 
such things for n
.
I think you have a backpack problem and dynamic programming is the correct way to solve it.
a source to share
Maybe have a look here http://en.wikipedia.org/wiki/Packing_problem and here http://en.wikipedia.org/wiki/Knapsack_problem might be inspiring ...
a source to share
For, N <= 7
you can just be exhaustive:
In C-ish pseudocode 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, placing them in the list, and adding it. If you want to play with optimization, you can even memoir it.
a source to share