giorgio93p / bin-packing
实现了具有容量下限的bin packing的分支定界算法
v1.0.2
2023-04-13 07:25 UTC
Requires
- php: >=7.2
Requires (Dev)
- friendsofphp/php-cs-fixer: *
- phpstan/phpstan: >=1.9.0
- phpunit/phpunit: *
README
该算法通过(几乎)穷举所有可能的解决方案来尝试找到最佳可能的解决方案(即具有更少数量的bin)。这意味着它相当慢,并且对于超过几十个项目的输入将不会终止。
您的项目需要实现 BinItem
接口。这包括仅包含一个 size(): int
方法的代码。这表示项目的尺寸。注意,它必须是一个严格正整数。BinItem
的 size()
方法应在常数时间内运行。
您可以将 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
。