knapsack.php

<?php
// http://en.wikipedia.org/wiki/Knapsack_problem
// http://upload.wikimedia.org/wikipedia/commons/c/c6/Knapsack_greedy.svg

// KNAPSACK BALANCER!
 
class Balancer
{
        public static function balance($items, $key)
        {
                $result = array();
                $maxWeight = floor(self::sum($items, $key) / 2);
                $numItems = count($items);
               
                $sack = self::buildSack($numItems, $maxWeight);
                
                
                for ($n = 1; $n <= $numItems; $n++)
                {
                        // loop all items
                        for ($weight = 1; $weight <= $maxWeight; $weight++)
                        {
                                $a = $sack[$n - 1][$weight]['value'];
                                $b = null;
                                $value = $items[$n - 1][$key];
                                if ($value <= $weight)
                                {
                                        $b = $value + $sack[$n - 1][$weight - $value]['value'];
                                }
                                $sack[$n][$weight]['value'] = ($b === null ? $a : max($a, $b));
                                $sack[$n][$weight]['take'] = ($b === null ? false : $b > $a);
                        }
                }
               
                $setA = array();
                $setB = array();
               
                for ($n = $numItems, $weight = $maxWeight; $n > 0; $n--)
                {
                        $item = $items[$n - 1];
                        $value = $item[$key];
                        if ($sack[$n][$weight]['take'])
                        {
                                $setA[] = $item;
                                $weight = $weight - $value;
                        }
                        else
                        {
                                $setB[] = $item;
                        }
                }

                return array($setA, $setB);
        }
       
        protected static function sum($items, $key)
        {
                $sum = 0;
                foreach ($items as $item)
                {
                        $sum += $item[$key];
                }
                return $sum;
        }
       
        protected static function buildSack($width, $height)
        {
                $sack = array();
                for ($x = 0; $x <= $width; $x++)
                {
                        $sack[$x] = array();
                        for ($y = 0; $y <= $height; $y++) {
                                $sack[$x][$y] = array(
                                        'value' => 0,
                                        'take' => false
                                );
                        }
                }
                                   
                return $sack;
        }
}
 
$packages = array(

        array('id' => 1, 'weight' => 9, 'value' => 10),
        array('id' => 2, 'weight' => 12, 'value' => 7),
        array('id' => 3, 'weight' => 2, 'value' => 1),
        array('id' => 4, 'weight' => 7, 'value' => 3),
        array('id' => 5, 'weight' => 5, 'value' => 2),
       
);
 
$t = microtime(true);
$sets = Balancer::balance($packages, 'value');
 
$setA = $sets[0];
$setB = $sets[1];
 
$sum = 0;
$sum_weight = 0;

foreach ($setA as $package)
{
        $sum += $package['value'];
        $sum_weight += $package['weight'];
}
echo "Set1: "."\r\n";
echo 'ValueSum: '.$sum."\r\n";
echo 'WeightSum: '.$sum_weight."\r\n\r\n";
 
$sum = 0;
$sum_weight = 0;

foreach ($setB as $package)
{
        $sum += $package['value'];
        $sum_weight += $package['weight'];
}

echo "Set2: "."\r\n";
echo 'ValueSum: '.$sum."\r\n";
echo 'WeightSum: '.$sum_weight."\r\n";
 
print_r($sets);
var_dump(microtime(true) - $t);