<?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);