遍历多个数组值以在另一个数组中填充存储桶的算法

Question

I can't think of a better way to phrase it, but here's what I want to do. I'm working on a package optimizer class for a shopping cart. The idea is that up to X widgets of varying type can fit in a single container. The catch is the widgets are not all the same size, so if say we have items A (largest), B, and C (smallest) we must use the A-sized X-item container.

Here's the dimensions array for my widgets

$widgets = array('WidgetA' => 
    array (
      'length' => 10,
      'width' => 10,
      'height' => 10,
      'weight' => 10
    ),
    'WidgetB' => 
    array (
      'length' => 9,
      'width' => 9,
      'height' => 9,
      'weight' => 9
    ),
    'WidgetC' => 
    array (
      'length' => 8,
      'width' => 8,
      'height' => 8,
      'weight' => 8
    )
);

Here's the array for the packaging options for these widgets, the key is the number of widgets that are supported by the related dimensions if it were all of the given widget type.

$packaging_options = array(
6 => 
array (
  'A' => 
  array (
    'length' => 100,
    'width' => 100,
    'height' => 100,
    'weight' => 100,
  ),
  'B' => 
  array (
    'length' => 90,
    'width' => 90,
    'height' => 90,
    'weight' => 90
  ),
  'C' => 
  array (
    'length' => 80,
    'width' => 80,
    'height' => 80,
    'weight' => 80
  )
),
5 => 
array (
  'A' => 
  array (
    'length' => 95,
    'width' => 95,
    'height' => 95,
    'weight' => 95,
  ),
  'B' => 
  array (
    'length' => 85,
    'width' => 85,
    'height' => 85,
    'weight' => 85
  ),
  'C' => 
  array (
    'length' => 75,
    'width' => 75,
    'height' => 75,
    'weight' => 75
  )
),
2 => 
array (
  'A' => 
  array (
    'length' => 20,
    'width' => 20,
    'height' => 20,
    'weight' => 20,
  ),
  'B' => 
  array (
    'length' => 18,
    'width' => 18,
    'height' => 18,
    'weight' => 18
  ),
  'C' => 
  array (
    'length' => 80,
    'width' => 80,
    'height' => 80,
    'weight' => 80
  )
),
1 => 
array (
  'A' => 
  array (
    'length' => 10,
    'width' => 10,
    'height' => 10,
    'weight' => 10,
  ),
  'B' => 
  array (
    'length' => 9,
    'width' => 9,
    'height' => 9,
    'weight' => 9
  ),
  'C' => 
  array (
    'length' => 8,
    'width' => 8,
    'height' => 8,
    'weight' => 8
  )
);

And here's a sample array of products from the cart. Key is the widget id and the value is the quantity.

$products = array(
   'A' => 14,
   'B' => 8,
   'C' => 23
);

I ultimately am trying to end up with an array of xpackages composed of entries that look like:

array(
   'length' => x,
   'height' => x,
   'width' => x,
   'weight' => (sum of the individual box weights allocated to this package)
);

I just can't figure out a good way to look through that products array to allocate to the boxes. It seems fairly simple when I just look at it, but the coding logic is just getting out of control and I know there has to be a better way than how I'm approaching it. I'm thinking recursion, but the solution is just not clicking for me.

Answer 1

I would suggest that you read up on the knapsack problem. This link suggests a few algorithms to solve it. They can be implemented pretty easily in whatever language.

http://en.wikipedia.org/wiki/Knapsack_problem

Most versions presented with dynamic programming only consider the weight of the products. If you read up a little bit more on variants of this problem, you will find that by adding a third dimension to your dynamic programming array you can consider the volume of the products.

Hope this helps! Good luck.

---

Ok I understand your problem a little bit better now. How about using an algorithm similar to this:

//widgets is an array of widgets sorted by volume
//count is an array holding the number of each 
Algorithm OptimizePackages(widgets[0..n-1], count[0..n-1])
    bin_stack <- initialize an empty stack of bins
    bin <- take a bin that can fit widgets[0]
    for(i = 0 to n-1) do
        for(j = 0 to count[i]) do
            if(bin.available_volume < widgets[i].volume) then
                bin_stack.push(bin)
                bin <- take a bin that can fit widgets[i]
            end if

            bin.add(widgets[i])
            bin.available_volume -= widgets[i].volume
        end
    end
    return bin_stack.to_array()

One of the limitations of this algorithm is that it might leave a small free volume on some bins. You can tweak it to remove this limitation if you have time to do the brain gymnastics it requires ;)