<?php
/* Этот алгоритм начинает перебор с ближайшего к сумме значения, поэтому он найдет комбинацию быстрее. Каждую итерацию
высчитывается максимальное количество купюр следущего номинала, то есть мы не не перебираем купюры, заведомо превышающие сумму.*/

declare(strict_types=1);
error_reporting(-1);

$money = 6600;

$bills = array( // Купюры по условию. Номинал купюры => количество купюр этого номинала
    5000 => 1,
    2000 => 4,
    500 => 1,
    200 => 3
);

$i=0;
foreach ($bills as $denomination => $amount) {
    $denominationOfBills[$i] = $denomination;
    $numberOfBills[$i] = range(0, $amount);
    $i+=1;
}

# Вышестоящим циклом создаются следующие массивы, которые до этого писались вручную.
/*$denominationOfBills = [ // Массив всех номиналов купюр
    0 => 5000,
    1 => 2000,
    2 => 500,
    3 => 200
];

$numberOfBills = [ // Количество купюр всех номиналов
    0 => range(0, 1),
    1 => range(0, 4),
    2 => range(0, 1),
    3 => range(0, 3)
]; */

function generateCombinations( array $numberOfBills, int $money, array $denominationOfBills, array $combination = [], $N = 0)
{

    # Высчитывается максимальное значение количества купюр перебираемого номинала, чтобы не превысить требуемую сумму
    if ($N < 4) { /* Если не поставить это условие, то будет пробовать высчитываться следующее после последнего(несуществующее) лимитное значение */
        $nextMaxLimit = floor(($money - sum($combination, $denominationOfBills)) / $denominationOfBills[$N]);
        if ($nextMaxLimit > max($numberOfBills[$N])) {
            $nextMaxLimit = max($numberOfBills[$N]);
        }
        $numberOfBills[$N] = range($nextMaxLimit, 0);
    }

    if (count($combination) == count($denominationOfBills)) { // Когда кол-во элементов комбинации == кол-ву предоставленных номиналов
        yield $combination; // Возвращаем комбинацию
    } else {
        foreach ($numberOfBills[$N] as $valueOnSquare) {
            yield from generateCombinations($numberOfBills, $money, $denominationOfBills, array_merge($combination, [$valueOnSquare]), $N + 1);
        }
    }
}

function sum(array $combination, array $denominationOfBills) : float // Функция высчитывающая сумму любой комбинации
{
    $sum = 0;
    $i = 0;
    foreach ($combination as $amount) {
        $sum += $amount * $denominationOfBills[$i];
        $i += 1;
    }
    return $sum;
}

$combinationGenerator = generateCombinations($numberOfBills, $money, $denominationOfBills);
foreach ($combinationGenerator as $combination) {
    if (sum($combination, $denominationOfBills) == $money) {
        echo "Комбинация с наименьшим кол-вом купюр надейна !" . PHP_EOL;
        print_r($combination);
        break;
    }
    //print_r($combination);

}
# Вывод в требуемом формате
for ($i = 0; $i < count($combination); $i++) {
    echo "{$denominationOfBills[$i]}x{$combination[$i]} ";
}