knapsack.php

    <?php
     
    // 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;
            }
    }
     
    $players = array(
            array('id' => 1, 'skill' => 1000),
            array('id' => 2, 'skill' => 1010),
            array('id' => 3, 'skill' => 1035),
            array('id' => 4, 'skill' => 1142),
            array('id' => 5, 'skill' => 1300),
            array('id' => 6, 'skill' => 900),
            array('id' => 7, 'skill' => 850),
            array('id' => 8, 'skill' => 1231),
            array('id' => 9, 'skill' => 1135),
            array('id' => 10, 'skill' => 1592)
    );
     
    $t = microtime(true);
    $sets = Balancer::balance($players, 'skill');
     
    $setA = $sets[0];
    $setB = $sets[1];
     
    $sum = 0;
    foreach ($setA as $player)
    {
            $sum += $player['skill'];
    }
    echo 't: '.$sum."\r\n";
     
    $sum = 0;
    foreach ($setB as $player)
    {
            $sum += $player['skill'];
    }
    echo 'ct: '.$sum."\r\n";
     
    //print_r($sets);
    var_dump(microtime(true) - $t);