giorgio93p/bin-packing

实现了具有容量下限的bin packing的分支定界算法

v1.0.2 2023-04-13 07:25 UTC

This package is auto-updated.

Last update: 2024-09-26 20:33:06 UTC


README

该算法通过(几乎)穷举所有可能的解决方案来尝试找到最佳可能的解决方案(即具有更少数量的bin)。这意味着它相当慢,并且对于超过几十个项目的输入将不会终止。

您的项目需要实现 BinItem 接口。这包括仅包含一个 size(): int 方法的代码。这表示项目的尺寸。注意,它必须是一个严格正整数。BinItemsize() 方法应在常数时间内运行。

您可以将 BinItem 的可迭代(例如 array 或 laravel Collection)实例传递给 BinPacking::pack,同时传递包装选项(bin的最小和最大尺寸)。再次提醒,尺寸必须是严格正整数。最小尺寸也可以是0。

BinPacking::pack 将返回一个包含bins的数组。每个bin都有一个 items() 方法,该方法返回输入中在该bin中的项目。

例如,

class MyClass implements \Gpits\BinPacking\BinItem
{
    public function size(): int
    {
        //fill this
    }
}

$items = MyClass::getAllItems();

$bins = \Gpits\BinPacking\BinPacking::pack($items, 150, 4000); // for min bin size 150 and max bin size 4000
foreach($bins as $bin){
    foreach($bin->items() as $item){
        //do something with
        $item;
        // where $item instanceof MyClass
    }
}

如果您有一个太大无法放入任何bin的项目,将抛出 BinPackingException