PHP Mysql逻辑循环表和优化输出

Question

不100%确定标题，请随意编辑，使其更通用，并对所有用户都有帮助。

我有一个订单捕获‘门户’，它允许订单被捕获。订单的一部分是数量或订单。

我现在需要处理订单，以便可以建立一个托盘，允许最佳使用托盘。

例如，包装托盘的尺寸可以是1.62立方米(1x1.2x1.35)

然后我在订单上有以下几项

产品代码，qty，总容量

第一、第二、第十、第五

第二、第三、第二、

第三、第三、二、五、二、三、二、二、三、二、三、三、四、三、四、四、三、三、四、二、二、三、二、二、三、二、三、三、四、四、

第四条，准准标准1、准标准标准0.15立方米

第五条.

我想要处理这个问题，我假设使用mysql事务，以便获得以下输出：

托盘1:产品1,2,5.总Volume=1.3立方米

托盘2:产品3,4.总Volume=1.35立方米

因此，为了澄清，脚本将采取第一个托盘0.5立方体，然后寻找下一个顺序，是最接近0.85的名单，以达到1.35立方米的目标。在这种情况下，是0.6。共计1.1立方体。剩下的空间现在是0.25立方体。列表中最近的项目现在是产品2@ 0.2立方体。总数现在1.3立方体和没有产品存在，即0.05立方体或更少这样托盘是完整的。下一个可用的产品现在是产品3@ 1.2立方体。因此，需要0.15或更少的产品。产品4是准确的体积，所以添加到托盘和关闭。

我希望这有助于澄清我的要求。

是否有mysql事务可以帮助此操作，或者是否需要使用php进行处理。

在这方面的任何帮助都将受到感谢，只是不确定如何构建这一逻辑。

感谢你一如既往地抽出时间，

​

​

mysql表如下：

​

​

Answer 1

这是经典的装箱问题，它是NP-硬的(也就是说，我们还没有计算出这个问题是否可以在多项式时间内解决)。找到最优的包装就等于尝试每一种可能的组合。

如果您不关心寻找最优解，那么您在问题中描述的贪婪的启发式(称为一次拟合递减)是一个合理的近似；还有其他的启发式方法可以保证总体上更优的结果，但它们变得相当复杂。

您可以按照以下方式在PHP中实现FFD (使用PDO进行数据库访问)：

define('PALLET_SIZE', 1 * 1.2 * 1.35);

$dbh = new PDO("mysql:dbname=$dbname", $username, $password);

$qry = $dbh->prepare('
  SELECT   code, qty, volume
  FROM     orders
  WHERE    order_id = :order
  ORDER BY volume DESC
');

$qry->execute(array(':order' => 123));

$pallets = array();
while ($order = $qry->fetch()) {
  if ($order['volume'] > PALLET_SIZE) die('item too big');

  for ($i = 1; $i <= $order['qty']; $i++) { // remove this loop if not needed
    $placed = false;
    foreach ($pallets as &$pallet) {
      if ($pallet['remaining'] >= $order['volume']) {
        $pallet['remaining'] -= $order['volume'];
        $pallet['items'][] = $order['code'];
        $placed = true;
        break;
      }
    }
    if (!$placed) $pallets[] = array(
      'remaining' => PALLET_SIZE - $order['volume'],
      'items' => array($order['code'])
    );
  }
}

print_r($pallets);

Answer 2

有mysql事务吗？

我猜你指的是mysql函数。

不，mysql中没有任何东西可以帮助您解决这个问题。这是个NP难题。解决这个问题的最有效的方法可能是一个遗传算法，但是您的数据中没有足够的信息来精确地实现这个功能--打包取决于形状(即所有维度)和体积。

如果你有尺寸，那么让人类设置包装要容易得多，而不是用代码来做。

作为一种快速解决方案，我会比较一组随机排序的列表的N个副本，遍历每一个创建完整的托盘，然后用最少的托盘(或其他需要的特性)选择列表。为N选择正确的值将取决于大小的分布，以及您想要花费多少时间来处理数据。

Answer 3

这类似于背包问题，这个问题只有通过尝试所有可能的组合才能完美地解决。随着可能的组合数量增加，这很快就成了一个问题。在你的例子中，会有33个！组合-相当大的数目。所以那条路可能不是我们想要走的..。

没有“开箱即用”的解决方案，尽管有用于背包问题这里的示例代码。也许能帮上忙。

几年前，我编写了一个程序，用类似的问题完成了一项合理的工作；伪代码类似于：

for each order
  while (unallocated items on order)
    create new pallet 
    while not (pallet = full)
      allocate largest remaining item smaller than remaining capacity to pallet 
    loop
  loop
next order

这个算法做得不错--船坞里的人都喜欢它，因为最大的物品总是排在装箱单的最上面(因此最终落在了堆叠的底部)。企业承认，算法不一定是最优的；在实践中，这只会对大订单产生影响，在这些订单中，算法的轻微改进可能会为我们节省一个托盘；在大多数情况下，提高算法的效率将意味着装运中的最后一个托盘几乎是空的。