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

$money = 6600;

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

$denominationOfBills = array( // Массив всех номиналов купюр
    0 => 5000,
    1 => 2000,
    2 => 500,
    3 => 200
);

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

function generateCombinations($numberOfBills, $money, $denominationOfBills, $arrayValues = [], $N = 0)
{

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

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

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

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

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


/*function greedyAlgorithm($money, $bills) //  Функция реализующая жадный алгоритм и подсчитывающая комбинацию купюр для выдачи нужной суммы.
 Алгоритм выдаёт комбинацию, даже при том условии, если нельзя выдать сумму полностью
{
    foreach ($bills as $denominationOfBills => $numberOfBills) {
        $greedyNumber = floor($money / $denominationOfBills);
        if ($greedyNumber > $numberOfBills) {
            $greedyNumber = $numberOfBills;
        }
        $arrayValues[] = $greedyNumber;
        $money -= $denominationOfBills * $greedyNumber;
    }
    return $arrayValues;
} */