<?php

error_reporting(-1);

$money = 6600;

$nominals = array(
    5000 => 1,
    2000 => 4,
    500 => 1,
    200 => 3
);
$banknotes = array(
    0 => range(0, 1),
    1 => range(0, 4),
    2 => range(0, 1),
    3 => range(0, 3)
);

$suitableCombinations = [];

function generateCombinations($n, $arrayValues, $banknotes, $N)
{
    global $money, $nominals, $suitableCombinations;
    if (count($arrayValues) == $n) {
        if (checkingCombination($arrayValues, $money, $nominals)) {
            $suitableCombinations[] = checkingCombination($arrayValues, $money, $nominals);
        }
        return $arrayValues;
    }

    foreach ($banknotes[$N] as $valueOnSquare) {
        generateCombinations($n, array_merge($arrayValues, [$valueOnSquare]), $banknotes, $N + 1);
    }

}

function checkingCombination($arrayValues, $money, $nominals)
{
    $i = 0;
    $sum = 0;
    foreach ($nominals as $nominal => $amount) {
        $sum += $arrayValues[$i] * $nominal; //Кол-во банкнот: {$arrayValue[$i]}. Номинал банкноты {$nominal}".
        $i += 1;
    }
    if ($sum == $money) {
        return $arrayValues;
    }
}

generateCombinations(4, [], $banknotes, 0);

echo "Подходящие комбинации".PHP_EOL;
print_r($suitableCombinations);

$bestCombination = [INF];
foreach ($suitableCombinations as $combination) {
    if (array_sum($combination) < array_sum($bestCombination)) {
        $bestCombination = $combination;
    }
}
echo "Лучшая комбинация с наименьшим количеством купюр".PHP_EOL;
print_r($bestCombination);

$answer = array_combine(array_keys($nominals), $bestCombination);

foreach ($answer as $nominals => $theNumberOfBills) {
    echo "{$theNumberOfBills}x{$nominals} ";
}