Skip to content

Instantly share code, notes, and snippets.

@dcabanaw
Created September 3, 2015 20:39
Show Gist options
  • Save dcabanaw/f7df7d36f9cfa5763a4f to your computer and use it in GitHub Desktop.
Save dcabanaw/f7df7d36f9cfa5763a4f to your computer and use it in GitHub Desktop.
Simple bin packing
<?php
class Bin
{
private $capacity;
private $content;
/**
* @param integer $capacity
* @param array $content
*/
public function __construct($capacity, array $content = [])
{
$this->capacity = $capacity;
$this->content = $content;
}
/**
* @param integer $item
*
* @return bool
*/
public function add($item)
{
if($this->addable($item))
{
array_push($this->content, $item);
return true;
}
return false;
}
/**
* @param integer $item
*
* @return bool
*/
public function addable($item)
{
return array_sum($this->content) + $item <= $this->capacity && $item > 0;
}
}
<?php
/**
* Class BinPool
* simple implementation of bin packing
*
* Given a pool of item sizes/weights, a bin capacity and a quantity of bins, can the pool be fully allocated
* to the bins and have room to add another item
*/
class BinPool
{
/**
* @var integer
*/
private $bin_capacity;
/**
* @var integer
*/
private $bin_quantity;
/**
* @var array
*/
private $pool;
/**
* @var Bin[]
*/
private $bins = [];
/**
* @param integer $bin_capacity the capacity of each bin
* @param integer $bin_quantity how many bins
* @param array $pool an array of numeric sizes/weights
*/
public function __construct($bin_capacity, $bin_quantity, array $pool = [])
{
$this->bin_capacity = $bin_capacity;
$this->bin_quantity = $bin_quantity;
$this->pool = $pool;
$this->bins = array_map(function() use ($bin_capacity, $bin_quantity) {
return new Bin($bin_capacity);}, array_pad([], $bin_quantity, null));
}
/**
* @param $item
*
* @return bool
*/
public function addable($item)
{
$this->validatePool();
$this->buildBins();
foreach($this->bins as $bin)
{
if($bin->addable($item))
{
return true;
}
}
return false;
}
private function validatePool()
{
if (!empty($this->pool))
{
if (max($this->pool) > $this->bin_capacity)
{
throw new RuntimeException("An item in the pool exceeds the max size of {$this->bin_capacity}");
}
}
}
private function buildBins()
{
while(!empty($this->pool))
{
$item = array_pop($this->pool);
foreach($this->bins as $bin)
{
if($bin->add($item))
{
break;
}
}
}
}
}
<?php
// autolader, incudes, etc...
$pool = [1,1,1,2,2];
$bp = new BinPool(4, 2, $pool);
$bp->isAddable(1); //true
$pool = [1,1,2,2,2];
$bp = new BinPool(4, 2, $pool);
$bp->isAddable(1); //false
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment