Packing Math Problem (PHP Experts Only)

PHP
21

Just interested if could solve it with the lucene method…

Instead of words/terms have product_ids or skus, and instead of term frequencies have quantities.

Here’s is a proof concept… ish.

The theory/math needs going over as done it from memory.

But given a list of packing solutions, (ie all combinations of products than can fit into a particular package) and precomputed their vectors…


<?php

class Vector
{
	static function dotProduct(array $a, array $b)
	{
		$r = 0;
		foreach($a as $i => $ai)
			if (isset($b[$i]))
				$r += $ai * $b[$i];
		return $r;
	}

	static function length(array $a)
	{
		return sqrt(array_reduce($a, function($r, $i) { return $r + ($i * $i); }, 0));
	}

	static function div(array $a, $n)
	{
		return array_map(function($i) use ($n) { return $i / $n; }, $a);
	}

	static function normalize(array $a)
	{
		return self::div($a, self::length($a));
	}
}

class Packer
{
	protected $solutions;
	protected $vectors;

	function __construct($solutions, $vectors)
	{
		$this->solutions = $solutions;
		$this->vectors = $vectors;
	}

	function pack(array $productsToPack)
	{
		$solution = array();
		while ($productsToPack)
		{
			$r = array();

			$productsToPackVector = Vector::normalize($productsToPack);

echo 'Packing ', json_encode($productsToPack), "\
";
			foreach($this->vectors as $solutionId => $vector)
			{
				$similarity = Vector::dotProduct($productsToPackVector, $vector);

echo ' -> ', json_encode($this->solutions[$solutionId]), ' ', $similarity, "\
";
				if ($similarity > 0)
					$r[$solutionId] = $similarity;
			}
			if ($r)
			{
				arsort($r);
				list($partialSolution, $similarity) = each($r);

echo ' Packed using ', json_encode($this->solutions[$partialSolution]), ' ', $similarity, "\
";
				foreach($this->solutions[$partialSolution] as $product => $quantity)
					if (isset($productsToPack[$product]))
					{
						$productsToPack[$product] -= $quantity;
						if (0 >= $productsToPack[$product])
							unset($productsToPack[$product]);
					}
				$solution[] = $partialSolution;
			}
			else
				throw new Exception('Unable to pack '.json_encode($productsToPack));
		}
		return $solution;
	}
}

$products = array(
	'orange',
	'apple',
	'banana',
);

$numberOfProducts = count($products);

$packingSolutions = array();
$packingSolutions[0] = array('orange' => 1);					// can fit 1 orange in
$packingSolutions[1] = array('orange' => 4);					// can fit 4 oranges in
$packingSolutions[2] = array('apple' => 1);						// can fit 1 apple in
$packingSolutions[3] = array('apple' => 3);						// can fit 3 apples in
$packingSolutions[4] = array('banana' => 1);					// can fit 1 banana in
$packingSolutions[5] = array('orange' => 2, 'apple' => 2);		// can fit 2 oranges & 2 apples in

$packingVectors = array();
foreach($packingSolutions as $packingSolutionId => $packedProducts)
	$packingVectors[$packingSolutionId] = Vector::normalize($packedProducts);


	$packer = new Packer($packingSolutions, $packingVectors);

$basket = array();
$basket['orange'] = 2;
$basket['apple'] = 3;

$solution = $packer->pack($basket);

echo "\
", 'Packing solution', "\
";
foreach($solution as $solutionId)
	echo json_encode($packingSolutions[$solutionId]), "\
";

PS the math definitely needs checking…

22

I don’t understand much about the code you have posted above but creating a list of available vectors after each product is added sounds like a good idea.

you can run through the avaliable vectors to see if a product fits.

23

If have 2 products called x, and y.

Every list of products can been seen as a point on a 2 dimensional graph.

2x’s and 1y… would be the point (2, 1) on the graph
3x’s and 0y would be (3, 0) and so on.

Now having two points, one is productsToPack and another is productsWeCanPackIntoAParticularBox.

If draw lines from origin (0,0) to both, the angle between them represents how similar they are, the smaller the angle, the more similar the both product-lists are.

24

What about adding to 2 products in the same box?

25

If correctly pregenerated all possible contents for each box, the above routine should use it.

Eg in the code above, there is a box that will take 2 oranges and 2 apples…


$packingSolutions[5] = array('orange' => 2, 'apple' => 2);	// can fit 2 oranges & 2 apples in

So if ask for 4 oranges and 3 apples…


$basket = array();
$basket['orange'] = 4;
$basket['apple'] = 3;
$solution = $packer->pack($basket);

It says to use 2 of the boxes than can hold 2 oranges & 2 apples.


{"orange":2,"apple":2}
{"orange":2,"apple":2}
26

Ah dawned on me where I went wrong with the math.
Want to compare distances, rather than the angles.

So given two lists of products with quantities, can determine how far apart they are.

Easy enough… sqrt((x1-x2)^2 + (y1-y2)^2) for two products x & y…

27

So work out all the boxes that hold similar contents to a basket, and the use the distance measure to pick the closest match.

28

is there anyway you could put some code down to do this?

Would just comparing available volume give a correct anwser?

29

Here is the corrected version…
Its still a long long way from being usable.

But seems to correctly compare two lists of products.


<?php

class Vector
{
	static function dotProduct(array $a, array $b)
    {
        $r = 0;
        foreach($a as $i => $ai)
            if (isset($b[$i]))
                $r += $ai * $b[$i];
        return $r;
    }

    static function length(array $a)
    {
        return sqrt(array_reduce($a, function($r, $i) { return $r + ($i * $i); }, 0));
    }

    static function div(array $a, $n)
    {
        return array_map(function($i) use ($n) { return $i / $n; }, $a);
    }

    static function normalize(array $a)
    {
        return self::div($a, self::length($a));
    }

	static function distance(array $a, array $b)
	{
		$d = 0;
		foreach($a as $i => $v)
			$d += pow($v - (isset($b[$i]) ? $b[$i] : 0), 2);

		foreach($b as $i => $v)
			if (!isset($a[$i]))
				$d += $v*$v;

		return sqrt($d);
	}
}

class Packer
{
	protected $boxes;
	protected $boxVectors;

    function __construct($boxes, $boxVectors)
    {
        $this->boxes = $boxes;
        $this->boxVectors = $boxVectors;
    }

	function pack(array $productsToPack)
	{
		$boxList = array();

		while ($productsToPack)
		{
			$productsToPackVector = Vector::normalize($productsToPack);

			$bestSimilarity = 0;
			$bestDistance = -1;
			$bestContents = -1;

			foreach($this->boxVectors as $boxId => $possibleContents)
			{
				foreach($possibleContents as $contents => $vector)
				{
					$similarity = Vector::dotProduct($productsToPackVector, $vector);
					if ($similarity > $bestSimilarity)
					{
						$bestBoxId = $boxId;
						$bestContents = $contents;
						$bestSimilarity = $similarity;
						$bestDistance = Vector::distance($productsToPack, $this->boxes[$boxId][$contents]);
					}
					else if ($similarity == $bestSimilarity)
					{
						$distance = Vector::distance($productsToPack, $this->boxes[$boxId][$contents]);
						if ($distance < $bestDistance)
						{
							if (0 == $distance)		 // productsToPack perfectly fit into box
							{
								$boxList[$boxId] = isset($boxList[$boxId]) ? $boxList[$boxId] + 1 : 1;
								return $boxList;
							}
							$bestDistance = $distance;
							$bestBoxId = $boxId;
							$bestContents = $contents;
						}
					}
				}
			}

			if ($bestDistance >= 0)
			{
				$boxList[$bestBoxId] = isset($boxList[$bestBoxId]) ? $boxList[$bestBoxId] + 1 : 1;
				foreach($this->boxes[$bestBoxId][$bestContents] as $product => $quantity)
					if (isset($productsToPack[$product]))
					{
						$productsToPack[$product] -= $quantity;
						if (0 >= $productsToPack[$product])
							unset($productsToPack[$product]);
					}
			}
			else
				throw new Exception('Unable to pack '. json_encode($productsToPack));
		}
		return $boxList;
	}
}

$products = array(
	'orange',
	'apple',
	'banana',
);

$numberOfProducts = count($products);

$boxes = array();

// First box can hold 16 apples or oranges, or mix of both...
$boxes[] = array(
		array('apple' => 16),
		array('apple' => 8, 'orange' => 8),
		array('orange' => 16),
);


// Second box can hold an apple or orange
$boxes[] = array(
	array('orange' => 1),
	array('apple' => 1)
);


// Third box can hold 4 apples or oranges, or mix of both...
$boxes[] = array(
	array('orange' => 4),
	array('apple' => 4),
	array('apple' => 2, 'orange' => 2)
);


$boxVectors = array();
foreach($boxes as $boxId => $possibleContents)
	foreach($possibleContents as $i => $products)
		$boxVectors[$boxId][$i] = Vector::normalize($products);

$packer = new Packer($boxes, $boxVectors);

$basket = array();
$basket['apple'] = 33;
$basket['orange'] = 10;

$solution = $packer->pack($basket);

echo 'Pack ', json_encode($basket), ' into ', "\
";
foreach($solution as $boxId => $quantity)
	echo ' ', $quantity, ' #', $boxId, $quantity == 1 ? ' box' : ' boxes', "\
";