5

我正在尝试找到计算运输所需包装箱尺寸的最佳方法。

我有 3 个不同尺寸的集装箱。我在数据库中定义了产品的宽度、长度、深度和质量。

我想知道如何找到需要运送的最小数量的盒子，以及考虑到购物车中物品的数量，这些盒子的最小尺寸。

我目前的“想法”是找到整个产品数组的最大宽度，根据它选择一个框，然后根据需要拆分订单……这似乎行不通。

我的盒子尺寸是： - 8 x 6 x 6 = 228 立方英寸 - 10 x 8 x 8 = 640 立方英寸 - 12.5 x 12.5 x 12.5 = 1953.125 立方英寸

产品定义如下：

 [Product] => Array
                (
                    [STOCK_CODE] => 010003
                    [Product_Slug] => GABA_010003
                    [ItemName] => GABA
                    [WHOLESALE_PRICE] => 17.47
                    [RETAIL_PRICE] => 24.95
                    [Brand] => 
                    [ProductLine] => 
                    [image_name] => 705077000440
                    [MASS] => 0.313
                    [Height] => 4.625
                    [Width] => 2.375
                    [Depth] => 2.375
                    [cubic_inches] => 26.087890625
                )

我研究过背包问题、包装问题等，但找不到解决方法。任何帮助都会很棒。

function shipping(){

        $this->CartProduct->unbindModel(
            array('belongsTo' => array('User'))
        );

        //find all cart products by current logged in user
        $cartItems = $this->CartProduct->find('all', array('conditions' => array('CartProduct.user_id' => $this->Auth->user('id'))));

        $i = 0;

        //get the max width, height, depth
        $maxHeight = 0;
        $maxWidth = 0;
        $maxDepth = 0;
        foreach($cartItems as $c){
            $cartItems[$i]['Product']['cubic_inches'] = $c['Product']['Height'] * $c['Product']['Width'] * $c['Product']['Depth'];
            $cartItems[$i]['CartProduct']['total_cubic_inches'] = ($c['Product']['Height'] * $c['Product']['Width'] * $c['Product']['Depth']) * $c['CartProduct']['qty'];

            if($c['Product']['Height'] > $maxHeight)
            {
                $maxHeight = $c['Product']['Height'];
            }

            if($c['Product']['Width'] > $maxWidth)
            {
                $maxWidth = $c['Product']['Width'];
            }
            if($c['Product']['Depth'] > $maxDepth)
            {
                $maxDepth = $c['Product']['Depth'];
            }
            $i++;
        }

        //possible containers 
        //8 x 6 x 6 = 228 ci
        //10 x 8 x 8 = 640 ci
        //12.5 x 12.5 x 12.5 = 1953.125

        $possibleContainers = array(
            1 => array(
                'Height' => 8,
                'Width' => 6,
                'Depth' => 6,
                'Cubic' => 228),
            2 => array(
                'Height' => 10,
                'Width' => 8,
                'Depth' => 8,
                'Cubic' => 640),
            3 => array(
                'Height' => 12.5,
                'Width' => 12.5,
                'Depth' => 12.5,
                'Cubic' => 1953.125)
        );



        $max = array(
            'Height' => $maxHeight, 
            'Width' => $maxWidth, 
            'Depth' => $maxDepth, 
        );

        pr($cartItems);
        pr($possibleContainers);
        die();  
    }
4

2 回答 2

2

至于获得最佳答案，那是 NP-Hard ... http://en.wikipedia.org/wiki/Bin_packing_problem

Wikipedia 上显示的贪心算法虽然可能相距甚远，但实际上可能适合您的情况。

但是，作为估计，您可以仅将项目的数量相加，然后应用低效率因素，然后使用尽可能小的盒子。

或者，您可以将物品分类成递减的体积，然后查看您可以进入当前的一组盒子，当您无法放入该物品时创建一个新盒子。但不确定您将如何处理不同的盒子尺寸。您也可能会更改盒子大小而不是创建新盒子。

深思熟虑。

于 2010-06-29T02:31:10.353 回答
2

这是一个技术含量低但可能的解决方案：

我们刚刚遇到了同样的问题。我决定采用我们的盒子尺寸，然后给每个产品一个百分比，说明它在每个盒子尺寸中占用了多少空间。我们的产品是自由形式的，可以稍微压扁，所以如果您的产品是绝对尺寸，您可能需要减少百分比以考虑以不同角度放入盒子中的产品等......同样对我们来说，我们能够始终放置盒子里的东西彼此成相同的角度，所以这也有助于使下面的方法更好地工作。

这假设有 3 个盒子大小：

  • 产品A
    • 盒子 A = 48% （2 个装在盒子里）
    • Box B = 30% （3 个装在一个盒子里）
    • 盒子 C = 12% （8 个装在盒子里）
  • 产品B
    • 方框 A = 24%
    • 方框 B = 15%
    • 方框 C = 7%

然后只需让您的代码为框 A、B 和 C 的购物车项目添加这些百分比......显然，如果任何低于 100%，一切都应该适合，如果你从上到下开始第一个低于 100%将适合您的产品并成为最小的盒子。如果您在包装时遇到任何不合适的情况，只需稍微减少您为该产品输入的百分比。

对于多箱装运，您只需要决定您想要作为组合做什么。上述方法最适用于单箱运输，但通过一些额外的逻辑可以很容易地适用于多箱运输。

于 2012-06-22T15:19:35.067 回答