循环和组合产品的最佳方式

Question

我正在寻找您对实现此目的的最佳方式的个人想法，因为我可以通过多种方式达到相同的目的。

我的店面有多个不同的小册子，可以任意组合订购。

每个小册子项目在数据库中都有长 x 宽 x 高和重量。它们的长 x 宽完全相同，只是厚度和重量不同。

我也有设置最大框尺寸。

我知道我可以在最大的盒子尺寸中容纳 10.5 的高度。

不过，我可以合并这些书以便运输。所以我想尽可能地填充盒子，然后重复直到我只有部分盒子。

我需要的最终结果是每个盒子及其重量的数组。

示例：

已订购商品

第 1 册的 100 张，厚度为 0.05，重量为 0.15
第 2 册的 200 张，厚度为 .07，重量为 .23

身高

100 * .05 = 5
200 * .07 = 14

权重

100 * .15 = 15
200 * .23 = 46

盒子 1 包含

第 2 册的 150
高度：150 * .07 = 10.5
重量：150 * .23 = 34.5

方框 2 包含

第 2 册中的 50 个和第 1 册中的 100 个
高度：(100 * .05) + (50 * .07) = 8.5
权重：(100 * .15) + (50 * .25) = 27.5

您将如何循环遍历信息以获得输出？从一个产品开始，计算高度，将其分成完整的盒子，计算这些盒子的重量并将每个完整的盒子添加到数组中，获取部分盒子的高度并继续下一个产品？或者……??

静态编码会很“简单”，但我正在尝试对其进行动态编码，这样我就不必在每次添加新产品时都回来。

-编辑-

这是我当前的循环，但这只是合计数量并分成盒子。现在的产品都是一样的尺寸/形状，所以当时效果很好。

    if($zip_code != '')
    {
        my $item_list = enc_sql_select_multi("SELECT * FROM `$PREF{shopping_carts_table}` WHERE `cart_id` = '$cart_id' AND `sold` = '0' AND `deleted_from_cart` = '0'");
        my $item_qty = '0';
        foreach my $k (sort { $a <=> $b } keys %$item_list)
        {
            $item_qty =~ s/,//g;
            my $item_id = $$item_list{$k}{id};
            my $item_qty_new = $$item_list{$k}{option1value};
            $item_qty_new =~ s/,//g;
            $item_qty = $item_qty + $item_qty_new;
        }
        if ($item_qty != '0')
            {
                $item_qty =~ s/,//g;
                if ( $item_qty == 25 )
                {
                    my $tempCount = $carton_specs{25}{boxNo};
                    $tempCount++;
                    $carton_specs{25}{boxNo} = $tempCount;
                }
                elsif ( $item_qty == 50 )
                {
                    my $tempCount = $carton_specs{50}{boxNo};
                    $tempCount++;
                    $carton_specs{50}{boxNo} = $tempCount;
                }
                elsif ( $item_qty == 100 )
                {
                    my $tempCount = $carton_specs{100}{boxNo};
                    $tempCount++;
                    $carton_specs{100}{boxNo} = $tempCount;
                }
                elsif ($item_qty > 100 && $item_qty < 5000)
                {
                    my $fullBoxCt = int($item_qty / 200);
                    my $tempCountFull = $carton_specs{200}{boxNo};
                    $tempCountFull = $tempCountFull + $fullBoxCt;
                    $carton_specs{200}{boxNo} = $tempCountFull;
                    my $partBoxQty = $item_qty - (200 * $fullBoxCt);
                    if ($partBoxQty != 0)
                    {
                        my $tempCountPart = $carton_specs{$partBoxQty}{boxNo};
                        $tempCountPart++;
                        $carton_specs{$partBoxQty}{boxNo} = $tempCountPart;
                    }
                }
                else
                {
                    @shipDetails =
                    (
                        {
                            Code => 1000,
                            Price => '0.00'
                        },
                        {
                            Code => 1500,
                            Price => '0.00'
                        }
                    );
                    return (@shipDetails);
                }
            }

Answer 1

这是一个bin-packing problem. The best optimal algorithm is Korf's。如果这对于您拥有的数据量来说太慢了，有多种算法可以更快地提供良好的近似答案。

Answer 2

这是 bin-packing 问题的一个经典例子，虽然我也不是数学家，但很多人都考虑过这个问题。所以：

对于这个问题，没有已知的最佳解可以在多项式时间内计算，并且看起来您的输入量可能非常大。因此，您应该采用以下启发式方法之一：

First Fit Algorithm: 将小册子一张一张地处理，放在第一个有足够容量的盒子里。如果没有这样的框，则必须启动一个新框并将其添加到可用框列表中。
Best Fit Algorithm：将小册子一张一张处理，放入最紧（剩余容量最小）的盒子里。如果没有可以容纳小册子的盒子，则必须启动一个新盒子并将其添加到可用盒子列表中。
First Fit Decreasing Algorithm：先将小册子按高度递减排序，然后执行首次拟合算法。在您的示例中，您将首先打包“Book 2”小册子。
Best Fit Decreasing Algorithm: 先按高度递减排序小册子，然后执行最佳拟合算法。

但是，当然，您的订单包含某类小册子的 N 项。我们将松散地采用上述算法中的“一次一个”处方。因此，如果你正在做，例如，第一个适合算法，那么当你找到第一个有能力容纳小册子的盒子时，很容易计算出这些小册子的最大数量 M，那个盒子可以容纳和一次最多处理 min(M, N_LEFT) 本小册子，其中 N_LEFT 是您还需要打包的该尺寸小册子的数量。对于其他三种算法中的任何一种也是如此。

您可以调查其他 bin-packing 启发式方法，以上只是其中的四个示例。我不能说一个在所有情况下都一定优于其他。我认为对其中任何一个的任何合理实施都会满足您的目的。无论如何，这是我的看法。

循环和组合产品的最佳方式

best way to loop through and combine products

javascript

arrays

web

foreach

cgi