php - 遍历多个数组值以填充另一个数组中的桶的算法

Question

我想不出更好的表达方式，但这就是我想做的。我正在为购物车开发一个包优化器类。这个想法是最多 X 个不同类型的小部件可以放在一个容器中。问题是小部件的大小不尽相同，因此如果说我们有项目 A(最大)、B 和 C(最小)，我们必须使用 A 大小的 X 项目容器。

这是我的小部件的维度数组

$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
    )
);

这里是这些小部件的封装选项的数组，关键是如果它们都是给定的小部件类型，则相关维度支持的小部件数量。

$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
  )
);

下面是购物车中的一组示例产品。键是小部件 ID，值是数量。

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

我最终试图得到一个 xpackages 数组，这些 xpackages 由看起来像这样的条目组成:

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

我只是想不出一个好的方法来查看产品数组以分配给盒子。当我只看它时，它似乎相当简单，但编码逻辑正在失控，我知道必须有比我正在接近它的方式更好的方法。我在考虑递归，但解决方案就是不适合我。

Answer 1

我建议您阅读背包问题。此链接建议了一些算法来解决它。它们可以很容易地用任何语言实现。

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

大多数采用动态规划的版本只考虑产品的重量。如果您阅读更多有关此问题变体的内容，您会发现通过向动态规划数组添加第三维，您可以考虑产品的体积。

希望对您有所帮助!祝你好运。

---

好的，我现在对你的问题有了更深的理解。使用与此类似的算法如何:

//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()

此算法的一个局限性是它可能会在某些 bin 上留下一个小的空闲空间。如果你有时间做它需要的大脑体操，你可以调整它来消除这个限制;)