<?php
// Сколько выдать
$input = 6600;
// Номиналы и количество имеющихся купюр
$bills = array(
    100 => 0,
    200 => 3,
    500 => 1,
    1000 => 0,
    2000 => 4,
    5000 => 1
);
 
$error = '';
if ($input < 0) {
    $error = 'Сумма меньше нуля';
} elseif (($input % 100) != 0) {
    $error = 'Число не кратно 100';
} else {
    // Упорядочить валюты по убыванию
    krsort($bills);
 
    // Удаляем из массива купюры которых нет в наличии
    $toDelete = array_keys($bills, 0);
    foreach ($toDelete as $bill) {
        unset($bills[$bill]);
    }
 
    $canIssue[0][0] = 0;
    $canIssue[0][1] = $bills;
    for ($sum = 1; $sum <= $input; ++$sum) {
        $canIssue[$sum][0] = INF;
        $canIssue[$sum][1] = $bills;
        $billsTmp = $bills;
        foreach ($billsTmp as $bill => $count) {
            if ($count == 0) {
                continue;
            }
            if (($sum >= $bill) && ($canIssue[$sum - $bill][0] + 1 < $canIssue[$sum][0])) {
                if ($canIssue[$sum - $bill][1][$bill] != 0) {
                    $canIssue[$sum][0] = $canIssue[$sum - $bill][0] + 1;
                    $billsTmp = $canIssue[$sum - $bill][1];
                    --$billsTmp[$bill];
                    $canIssue[$sum][1] = $billsTmp;
                }
            }
        }
    }
 
    $sum = $input;
    // Количество выданных купюр
    $issued = array_fill_keys(array_keys($bills), 0);
    if ($canIssue[$sum][0] == INF) {
        $error = 'Недостаточно купюр';
    } else {
        while ($sum > 0) {
            foreach ($bills as $bill => $count) {
                if (isset($canIssue[$sum - $bill][0])) {
                    if ($canIssue[$sum - $bill][0] == $canIssue[$sum][0] - 1) {
                        ++$issued[$bill];
                        $sum -= $bill;
                        break;
                    }
                }
            }
        }
    }
 
    krsort($issued);
    $billsCount = '';
    foreach ($issued as $bill => $count) {
        if ($count != 0) {
            $billsCount .= "{$count}x{$bill} ";
        }
    }
}
 
echo "Сумма: {$input}\n";
if ($error != '') {
    echo "Выдача невозможна: {$error}\n";
} else {
    echo "Выдача возможна, число купюр:\n{$billsCount}";
}

PD9waHAKLy8g0KHQutC+0LvRjNC60L4g0LLRi9C00LDRgtGMCiRpbnB1dCA9IDY2MDA7Ci8vINCd0L7QvNC40L3QsNC70Ysg0Lgg0LrQvtC70LjRh9C10YHRgtCy0L4g0LjQvNC10Y7RidC40YXRgdGPINC60YPQv9GO0YAKJGJpbGxzID0gYXJyYXkoCiAgICAxMDAgPT4gMCwKICAgIDIwMCA9PiAzLAogICAgNTAwID0+IDEsCiAgICAxMDAwID0+IDAsCiAgICAyMDAwID0+IDQsCiAgICA1MDAwID0+IDEKKTsKCiRlcnJvciA9ICcnOwppZiAoJGlucHV0IDwgMCkgewogICAgJGVycm9yID0gJ9Ch0YPQvNC80LAg0LzQtdC90YzRiNC1INC90YPQu9GPJzsKfSBlbHNlaWYgKCgkaW5wdXQgJSAxMDApICE9IDApIHsKICAgICRlcnJvciA9ICfQp9C40YHQu9C+INC90LUg0LrRgNCw0YLQvdC+IDEwMCc7Cn0gZWxzZSB7CiAgICAvLyDQo9C/0L7RgNGP0LTQvtGH0LjRgtGMINCy0LDQu9GO0YLRiyDQv9C+INGD0LHRi9Cy0LDQvdC40Y4KICAgIGtyc29ydCgkYmlsbHMpOwoKICAgIC8vINCj0LTQsNC70Y/QtdC8INC40Lcg0LzQsNGB0YHQuNCy0LAg0LrRg9C/0Y7RgNGLINC60L7RgtC+0YDRi9GFINC90LXRgiDQsiDQvdCw0LvQuNGH0LjQuAogICAgJHRvRGVsZXRlID0gYXJyYXlfa2V5cygkYmlsbHMsIDApOwogICAgZm9yZWFjaCAoJHRvRGVsZXRlIGFzICRiaWxsKSB7CiAgICAgICAgdW5zZXQoJGJpbGxzWyRiaWxsXSk7CiAgICB9CgogICAgJGNhbklzc3VlWzBdWzBdID0gMDsKICAgICRjYW5Jc3N1ZVswXVsxXSA9ICRiaWxsczsKICAgIGZvciAoJHN1bSA9IDE7ICRzdW0gPD0gJGlucHV0OyArKyRzdW0pIHsKICAgICAgICAkY2FuSXNzdWVbJHN1bV1bMF0gPSBJTkY7CiAgICAgICAgJGNhbklzc3VlWyRzdW1dWzFdID0gJGJpbGxzOwogICAgICAgICRiaWxsc1RtcCA9ICRiaWxsczsKICAgICAgICBmb3JlYWNoICgkYmlsbHNUbXAgYXMgJGJpbGwgPT4gJGNvdW50KSB7CiAgICAgICAgICAgIGlmICgkY291bnQgPT0gMCkgewogICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYgKCgkc3VtID49ICRiaWxsKSAmJiAoJGNhbklzc3VlWyRzdW0gLSAkYmlsbF1bMF0gKyAxIDwgJGNhbklzc3VlWyRzdW1dWzBdKSkgewogICAgICAgICAgICAgICAgaWYgKCRjYW5Jc3N1ZVskc3VtIC0gJGJpbGxdWzFdWyRiaWxsXSAhPSAwKSB7CiAgICAgICAgICAgICAgICAgICAgJGNhbklzc3VlWyRzdW1dWzBdID0gJGNhbklzc3VlWyRzdW0gLSAkYmlsbF1bMF0gKyAxOwogICAgICAgICAgICAgICAgICAgICRiaWxsc1RtcCA9ICRjYW5Jc3N1ZVskc3VtIC0gJGJpbGxdWzFdOwogICAgICAgICAgICAgICAgICAgIC0tJGJpbGxzVG1wWyRiaWxsXTsKICAgICAgICAgICAgICAgICAgICAkY2FuSXNzdWVbJHN1bV1bMV0gPSAkYmlsbHNUbXA7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgJHN1bSA9ICRpbnB1dDsKICAgIC8vINCa0L7Qu9C40YfQtdGB0YLQstC+INCy0YvQtNCw0L3QvdGL0YUg0LrRg9C/0Y7RgAogICAgJGlzc3VlZCA9IGFycmF5X2ZpbGxfa2V5cyhhcnJheV9rZXlzKCRiaWxscyksIDApOwogICAgaWYgKCRjYW5Jc3N1ZVskc3VtXVswXSA9PSBJTkYpIHsKICAgICAgICAkZXJyb3IgPSAn0J3QtdC00L7RgdGC0LDRgtC+0YfQvdC+INC60YPQv9GO0YAnOwogICAgfSBlbHNlIHsKICAgICAgICB3aGlsZSAoJHN1bSA+IDApIHsKICAgICAgICAgICAgZm9yZWFjaCAoJGJpbGxzIGFzICRiaWxsID0+ICRjb3VudCkgewogICAgICAgICAgICAgICAgaWYgKGlzc2V0KCRjYW5Jc3N1ZVskc3VtIC0gJGJpbGxdWzBdKSkgewogICAgICAgICAgICAgICAgICAgIGlmICgkY2FuSXNzdWVbJHN1bSAtICRiaWxsXVswXSA9PSAkY2FuSXNzdWVbJHN1bV1bMF0gLSAxKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICsrJGlzc3VlZFskYmlsbF07CiAgICAgICAgICAgICAgICAgICAgICAgICRzdW0gLT0gJGJpbGw7CiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICBrcnNvcnQoJGlzc3VlZCk7CiAgICAkYmlsbHNDb3VudCA9ICcnOwogICAgZm9yZWFjaCAoJGlzc3VlZCBhcyAkYmlsbCA9PiAkY291bnQpIHsKICAgICAgICBpZiAoJGNvdW50ICE9IDApIHsKICAgICAgICAgICAgJGJpbGxzQ291bnQgLj0gInskY291bnR9eHskYmlsbH0gIjsKICAgICAgICB9CiAgICB9Cn0KCmVjaG8gItCh0YPQvNC80LA6IHskaW5wdXR9XG4iOwppZiAoJGVycm9yICE9ICcnKSB7CiAgICBlY2hvICLQktGL0LTQsNGH0LAg0L3QtdCy0L7Qt9C80L7QttC90LA6IHskZXJyb3J9XG4iOwp9IGVsc2UgewogICAgZWNobyAi0JLRi9C00LDRh9CwINCy0L7Qt9C80L7QttC90LAsINGH0LjRgdC70L4g0LrRg9C/0Y7RgDpcbnskYmlsbHNDb3VudH0iOwp9