所以,以下看起来(不可否认)非常丑陋,除了你的三个例子之外,我还没有测试过它,但是在这里：

class Ball {
    private $color;
    public function __construct($color) {
        $this->color = $color;
    }
    public function getColor() {
        return $this->color;
    }
}
class Ball_resource extends Ball {
    private $num_available;

    public function __construct($color,$number) {
        parent::__construct($color);
        $this->num_available = $number;
    }
    public function take() {
        $this->num_available--;
    }

    public function isExhausted() {
        return $this->num_available <= 0;
    }
}
class Person {
    /**
     *
     * @VAR Ball
     */
    private $Allowed_balls = array();

    public function addConstraint($color) {
        $this->allowed_balls[$color] = new Ball($color);
        return $this;
    }
    public function getConstraints() {
        return $this->allowed_balls;
    }

    public function getNumberOfconstraints() {
        return count($this->allowed_balls);
    }

    /**
     * return true if removal was successful; false otherwise
     */
    public function removeConstraint(Ball $ball) { // todo remove
        if (isset ($this->allowed_balls [$ball->getColor()])) {
            unset ($this->allowed_balls [$ball->getColor()]);
            return true;
        }
        else {
            // this means our puzzle isn't solvable
            return false;
        }
    }
}
class Simplifier {
    /**
     *
     * @var Person
     */
    private $persons = array ();
    /**
     *
     * @var Ball_resource
     */
    private $availableBalls = array ();

    public function addPerson(Person $person) {
        $this->persons[] = $person;
        return $this;
    }
    public function addBallRessource(Ball_resource $ball_resource) {
        $this->availableBalls[] = $ball_resource;
        return $this;
    }


    public function getChoices() {      
        $queue = $this->persons; // shallow copy

        while (count($queue) > 0) {
            // find most constrained person(s)
            $numberOfConstraints = 1; // each person must have at least one constraint
            while (true) {
                $resolve_queue = array();
                foreach($queue as $person) {
                    if ($person->getNumberOfConstraints() === $numberOfConstraints) {
                        $resolve_queue[] = $person;
                    }
                }
                // find mutually dependent constraint groups connected with a person
                $First_run = true;
                foreach ($resolve_queue as $startPerson) {
                    // check if we havent already been removed via dependencies
                    if ($first_run || !self::contains($queue,$startPerson)) {
                        $dependent_persons = $this->findMutuallyDependentPersons($startPerson,$resolve_queue);
                        // make a set out of their combined constraints
                        $combinedConstraints = $this->getConstraintsSet($dependent_persons);
                        $this->adjustResources($dependent_persons);
                        $this->removeFromQueue($dependent_persons,$queue);
                        // substract each ball of this set from all less constrained persons
                        $this->substractConstraintsFroMLessConstrainedPersons($queue,$combinedConstraints,$numberOfConstraints);
                        $first_run = false;
                        continue 3;
                    }
                }
                $numberOfConstraints++;
            }

        }
        return $this->persons; // has been altered implicitly   
    }

    private static function contains(array $haystack,Person $needle) {
        foreach ($haystack as $person) {
            if ($person === $needle) return true;
        }
        return false;
    }

    private function findMutuallyDependentPersons(Person $startPerson,array $persons) {
        // add recursion
        $output = array();
        //$output[] = $startPerson;
        foreach($persons as $person) {
            foreach ( $person->getConstraints () as $constraint ) {
                foreach ( $startPerson->getConstraints () as $targetConstraint ) {
                    if ($constraint->getColor () === $targetConstraint->getColor ()) {
                        $output [] = $person;
                        continue 3;
                    }
                }
            }   
        }
        return $output;
    }

    private function getConstraintsSet(array $persons) {
        $output = array();
        foreach ($persons as $person) {
            foreach ($person->getConstraints() as $constraint) {
                foreach($output as $savedConstraint) {
                    if ($savedConstraint->getColor() === $constraint->getColor()) continue 2;                   
                }
                $output[] = $constraint;
            }
        }
        return $output;
    }

    private function substractConstraintsFromLessConstrainedPersons(array $persons,array $constraints,$constraintThreshold) {
        foreach ($persons as $person) {
            if ($person->getNumberOfConstraints() > $constraintThreshold) {
                foreach($constraints as $constraint) {
                    foreach($this->availableBalls as $availableBall) {
                        if ($availableBall->isExhausted()) {
                            $person->removeConstraint($constraint);
                        }
                    }                   
                }
            }
        }
    }

    private function adjustResources(array $persons) {
        foreach($persons as $person) {
            foreach($person->getConstraints() as $constraint) {
                foreach($this->availableBalls as &$availableBall) {
                    if ($availableBall->getColor() === $constraint->getColor()) {
                        $availableBall->take();
                    }
                }
            }
        }
    }

    private function removeFromQueue(array $persons,array &$queue) {       
        foreach ($persons as $person) {
            foreach ($queue as $key => &$availablePerson) {
                if ($availablePerson === $person) {
                    unset($queue[$key]);
                }
            }
        }
    }
}

整个事情被称为这样：

// Example 2
{
    $person1 = new Person();
    $person1->addConstraint("R")->addConstraint("R")->addConstraint("G")->addConstraint("B")->addConstraint("B")->addConstraint("B")->addConstraint("B");
    $person2 = new Person();
    $person2->addConstraint("R")->addConstraint("R")->addConstraint("G");
    $person3 = new Person();
    $person3->addConstraint("R")->addConstraint("R")->addConstraint("G");
    $person4 = new Person();
    $person4->addConstraint("R")->addConstraint("R");

    $redBalls = new Ball_resource("R",2);
    $greenBalls = new Ball_resource("G",1);
    $blueBalls = new Ball_resource("B",4);

    $simplifier = new Simplifier();
    $simplifier->addPerson($person1)->addPerson($person2)->addPerson($person3)->addPerson($person4);
    $simplifier->addBallRessource($redBalls)->addBallRessource($greenBalls)->addBallRessource($blueBalls);
    $output = $simplifier->getChoices();

    print_r($output);
}

同样对于例3：

// Example 3
{
    $person1 = new Person();
    $person1->addConstraint("R")->addConstraint("G")->addConstraint("B")->addConstraint("Y");
    $person2 = new Person();
    $person2->addConstraint("R")->addConstraint("G");
    $person3 = new Person();
    $person3->addConstraint("G")->addConstraint("B");
    $person4 = new Person();
    $person4->addConstraint("R")->addConstraint("B");

    $redBalls = new Ball_resource("R",1);
    $greenBalls = new Ball_resource("G",1);
    $yellowBalls = new Ball_resource("Y",1);   

    $simplifier = new Simplifier();
    $simplifier->addPerson($person1)->addPerson($person2)->addPerson($person3)->addPerson($person4);
    $simplifier->addBallRessource($redBalls)->addBallRessource($greenBalls)->addBallRessource($blueBalls)->addBallRessource($yellowBalls);
    $output = $simplifier->getChoices();

    print_r($output);
}

为简洁起见,我省略了原始输出.但是对于第二个例子,它基本上等于你在问题中的最后一个列表,而对于例3,它产生相当于：

Person 1: Y
Person 2: RG
Person 3: GB
Person 4: RB