<?php
header("Content-Type: text/plain; charset=utf-8");
 
$amount = 11000;
 
$notes_available = [
    100  => 1,
    200  => 1,
    500  => 1,
    2000 => 4,
    5000 => 4,
];
 
krsort($notes_available, SORT_NUMERIC);
 
function check_withdraw($amount, $notes, $current_notes = []){
    static $withdraw = [];
 
    foreach($notes as $nominal => $quantity){
        /* вычисляем максимальное количество банкнот текущего номинала для выдачи остатка */
        $needed = (int)($amount / $nominal);
 
        if ($quantity >= $needed):
            $current_quantity = $needed;
        else:
            $current_quantity = $quantity;
        endif;
 
        /* вычисляем сумму для выдачи текущей банкнотой */
        $current_summ = $current_quantity * $nominal;
 
        /* убираем использованную валюту из массива, чтобы передать остальные в следующие итерации */
        unset($notes[$nominal]);
 
        /* создаю отдельный массив с валютами для следующей итерации,
           потому что текущий будет использоваться дальше в foreach */
        $next_current_notes = $current_notes;
 
        /* если купюр > 0, добавляем их количество и номинал в текущий набор в итерации */
        if($current_quantity)
            $next_current_notes[$nominal] = $current_quantity;
 
        /* если остаток равен 0 - добавляем в массив выдачи */
        if(!($amount - $current_summ)){
            $withdraw[] = $next_current_notes;
        }
 
        check_withdraw($amount - $current_summ, $notes, $next_current_notes);
    }
 
    /* на выходе получаются все возможные комбинации купюр, при обработке я беру первую */
    return $withdraw;
}
 
function get_message($withdraw, $amount){
    echo "Сумма $amount:\n";
    if(!empty($withdraw[0])){
 
        echo "Выдача возможна, число купюр:\n";
        foreach($withdraw[0] as $nominal => $quantity){
            echo $nominal."x".$quantity." ";
        }
    }else{
        echo "Выдача невозможна.";
    }
}
 
$withdraw = check_withdraw($amount, $notes_available);
 
get_message($withdraw, $amount);

PD9waHAKaGVhZGVyKCJDb250ZW50LVR5cGU6IHRleHQvcGxhaW47IGNoYXJzZXQ9dXRmLTgiKTsKCiRhbW91bnQgPSAxMTAwMDsKCiRub3Rlc19hdmFpbGFibGUgPSBbCiAgICAxMDAgID0+IDEsCiAgICAyMDAgID0+IDEsCiAgICA1MDAgID0+IDEsCiAgICAyMDAwID0+IDQsCiAgICA1MDAwID0+IDQsCl07CgprcnNvcnQoJG5vdGVzX2F2YWlsYWJsZSwgU09SVF9OVU1FUklDKTsKCmZ1bmN0aW9uIGNoZWNrX3dpdGhkcmF3KCRhbW91bnQsICRub3RlcywgJGN1cnJlbnRfbm90ZXMgPSBbXSl7CiAgICBzdGF0aWMgJHdpdGhkcmF3ID0gW107CgogICAgZm9yZWFjaCgkbm90ZXMgYXMgJG5vbWluYWwgPT4gJHF1YW50aXR5KXsKICAgICAgICAvKiDQstGL0YfQuNGB0LvRj9C10Lwg0LzQsNC60YHQuNC80LDQu9GM0L3QvtC1INC60L7Qu9C40YfQtdGB0YLQstC+INCx0LDQvdC60L3QvtGCINGC0LXQutGD0YnQtdCz0L4g0L3QvtC80LjQvdCw0LvQsCDQtNC70Y8g0LLRi9C00LDRh9C4INC+0YHRgtCw0YLQutCwICovCiAgICAgICAgJG5lZWRlZCA9IChpbnQpKCRhbW91bnQgLyAkbm9taW5hbCk7CgogICAgICAgIGlmICgkcXVhbnRpdHkgPj0gJG5lZWRlZCk6CiAgICAgICAgICAgICRjdXJyZW50X3F1YW50aXR5ID0gJG5lZWRlZDsKICAgICAgICBlbHNlOgogICAgICAgICAgICAkY3VycmVudF9xdWFudGl0eSA9ICRxdWFudGl0eTsKICAgICAgICBlbmRpZjsKCiAgICAgICAgLyog0LLRi9GH0LjRgdC70Y/QtdC8INGB0YPQvNC80YMg0LTQu9GPINCy0YvQtNCw0YfQuCDRgtC10LrRg9GJ0LXQuSDQsdCw0L3QutC90L7RgtC+0LkgKi8KICAgICAgICAkY3VycmVudF9zdW1tID0gJGN1cnJlbnRfcXVhbnRpdHkgKiAkbm9taW5hbDsKCiAgICAgICAgLyog0YPQsdC40YDQsNC10Lwg0LjRgdC/0L7Qu9GM0LfQvtCy0LDQvdC90YPRjiDQstCw0LvRjtGC0YMg0LjQtyDQvNCw0YHRgdC40LLQsCwg0YfRgtC+0LHRiyDQv9C10YDQtdC00LDRgtGMINC+0YHRgtCw0LvRjNC90YvQtSDQsiDRgdC70LXQtNGD0Y7RidC40LUg0LjRgtC10YDQsNGG0LjQuCAqLwogICAgICAgIHVuc2V0KCRub3Rlc1skbm9taW5hbF0pOwoKICAgICAgICAvKiDRgdC+0LfQtNCw0Y4g0L7RgtC00LXQu9GM0L3Ri9C5INC80LDRgdGB0LjQsiDRgSDQstCw0LvRjtGC0LDQvNC4INC00LvRjyDRgdC70LXQtNGD0Y7RidC10Lkg0LjRgtC10YDQsNGG0LjQuCwKICAgICAgICAgICDQv9C+0YLQvtC80YMg0YfRgtC+INGC0LXQutGD0YnQuNC5INCx0YPQtNC10YIg0LjRgdC/0L7Qu9GM0LfQvtCy0LDRgtGM0YHRjyDQtNCw0LvRjNGI0LUg0LIgZm9yZWFjaCAqLwogICAgICAgICRuZXh0X2N1cnJlbnRfbm90ZXMgPSAkY3VycmVudF9ub3RlczsKICAgICAgICAKICAgICAgICAvKiDQtdGB0LvQuCDQutGD0L/RjtGAID4gMCwg0LTQvtCx0LDQstC70Y/QtdC8INC40YUg0LrQvtC70LjRh9C10YHRgtCy0L4g0Lgg0L3QvtC80LjQvdCw0Lsg0LIg0YLQtdC60YPRidC40Lkg0L3QsNCx0L7RgCDQsiDQuNGC0LXRgNCw0YbQuNC4ICovCiAgICAgICAgaWYoJGN1cnJlbnRfcXVhbnRpdHkpCiAgICAgICAgICAgICRuZXh0X2N1cnJlbnRfbm90ZXNbJG5vbWluYWxdID0gJGN1cnJlbnRfcXVhbnRpdHk7CgogICAgICAgIC8qINC10YHQu9C4INC+0YHRgtCw0YLQvtC6INGA0LDQstC10L0gMCAtINC00L7QsdCw0LLQu9GP0LXQvCDQsiDQvNCw0YHRgdC40LIg0LLRi9C00LDRh9C4ICovCiAgICAgICAgaWYoISgkYW1vdW50IC0gJGN1cnJlbnRfc3VtbSkpewogICAgICAgICAgICAkd2l0aGRyYXdbXSA9ICRuZXh0X2N1cnJlbnRfbm90ZXM7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIGNoZWNrX3dpdGhkcmF3KCRhbW91bnQgLSAkY3VycmVudF9zdW1tLCAkbm90ZXMsICRuZXh0X2N1cnJlbnRfbm90ZXMpOwogICAgfQoKICAgIC8qINC90LAg0LLRi9GF0L7QtNC1INC/0L7Qu9GD0YfQsNGO0YLRgdGPINCy0YHQtSDQstC+0LfQvNC+0LbQvdGL0LUg0LrQvtC80LHQuNC90LDRhtC40Lgg0LrRg9C/0Y7RgCwg0L/RgNC4INC+0LHRgNCw0LHQvtGC0LrQtSDRjyDQsdC10YDRgyDQv9C10YDQstGD0Y4gKi8KICAgIHJldHVybiAkd2l0aGRyYXc7Cn0KCmZ1bmN0aW9uIGdldF9tZXNzYWdlKCR3aXRoZHJhdywgJGFtb3VudCl7CiAgICBlY2hvICLQodGD0LzQvNCwICRhbW91bnQ6XG4iOwogICAgaWYoIWVtcHR5KCR3aXRoZHJhd1swXSkpewoKICAgICAgICBlY2hvICLQktGL0LTQsNGH0LAg0LLQvtC30LzQvtC20L3QsCwg0YfQuNGB0LvQviDQutGD0L/RjtGAOlxuIjsKICAgICAgICBmb3JlYWNoKCR3aXRoZHJhd1swXSBhcyAkbm9taW5hbCA9PiAkcXVhbnRpdHkpewogICAgICAgICAgICBlY2hvICRub21pbmFsLiJ4Ii4kcXVhbnRpdHkuIiAiOwogICAgICAgIH0KICAgIH1lbHNlewogICAgICAgIGVjaG8gItCS0YvQtNCw0YfQsCDQvdC10LLQvtC30LzQvtC20L3QsC4iOwogICAgfQp9Cgokd2l0aGRyYXcgPSBjaGVja193aXRoZHJhdygkYW1vdW50LCAkbm90ZXNfYXZhaWxhYmxlKTsKCmdldF9tZXNzYWdlKCR3aXRoZHJhdywgJGFtb3VudCk7