<?php
header("Content-Type: text/plain; charset=utf-8");
 
$amount = 5600;
 
$notes_available = [
    100  => 0,
    200  => 3,
    500  => 1,
    2000 => 4,
    5000 => 1,
];
 
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);

PD9waHAKaGVhZGVyKCJDb250ZW50LVR5cGU6IHRleHQvcGxhaW47IGNoYXJzZXQ9dXRmLTgiKTsKCiRhbW91bnQgPSA1NjAwOwoKJG5vdGVzX2F2YWlsYWJsZSA9IFsKICAgIDEwMCAgPT4gMCwKICAgIDIwMCAgPT4gMywKICAgIDUwMCAgPT4gMSwKICAgIDIwMDAgPT4gNCwKICAgIDUwMDAgPT4gMSwKXTsKCmtyc29ydCgkbm90ZXNfYXZhaWxhYmxlLCBTT1JUX05VTUVSSUMpOwoKZnVuY3Rpb24gY2hlY2tfd2l0aGRyYXcoJGFtb3VudCwgJG5vdGVzLCAkY3VycmVudF9ub3RlcyA9IFtdKXsKICAgIHN0YXRpYyAkd2l0aGRyYXcgPSBbXTsKCiAgICBmb3JlYWNoKCRub3RlcyBhcyAkbm9taW5hbCA9PiAkcXVhbnRpdHkpewogICAgICAgIC8qINCy0YvRh9C40YHQu9GP0LXQvCDQvNCw0LrRgdC40LzQsNC70YzQvdC+0LUg0LrQvtC70LjRh9C10YHRgtCy0L4g0LHQsNC90LrQvdC+0YIg0YLQtdC60YPRidC10LPQviDQvdC+0LzQuNC90LDQu9CwINC00LvRjyDQstGL0LTQsNGH0Lgg0L7RgdGC0LDRgtC60LAgKi8KICAgICAgICAkbmVlZGVkID0gKGludCkoJGFtb3VudCAvICRub21pbmFsKTsKCiAgICAgICAgaWYgKCRxdWFudGl0eSA+PSAkbmVlZGVkKToKICAgICAgICAgICAgJGN1cnJlbnRfcXVhbnRpdHkgPSAkbmVlZGVkOwogICAgICAgIGVsc2U6CiAgICAgICAgICAgICRjdXJyZW50X3F1YW50aXR5ID0gJHF1YW50aXR5OwogICAgICAgIGVuZGlmOwoKICAgICAgICAvKiDQstGL0YfQuNGB0LvRj9C10Lwg0YHRg9C80LzRgyDQtNC70Y8g0LLRi9C00LDRh9C4INGC0LXQutGD0YnQtdC5INCx0LDQvdC60L3QvtGC0L7QuSAqLwogICAgICAgICRjdXJyZW50X3N1bW0gPSAkY3VycmVudF9xdWFudGl0eSAqICRub21pbmFsOwoKICAgICAgICAvKiDRg9Cx0LjRgNCw0LXQvCDQuNGB0L/QvtC70YzQt9C+0LLQsNC90L3Rg9GOINCy0LDQu9GO0YLRgyDQuNC3INC80LDRgdGB0LjQstCwLCDRh9GC0L7QsdGLINC/0LXRgNC10LTQsNGC0Ywg0L7RgdGC0LDQu9GM0L3Ri9C1INCyINGB0LvQtdC00YPRjtGJ0LjQtSDQuNGC0LXRgNCw0YbQuNC4ICovCiAgICAgICAgdW5zZXQoJG5vdGVzWyRub21pbmFsXSk7CgogICAgICAgIC8qINGB0L7Qt9C00LDRjiDQvtGC0LTQtdC70YzQvdGL0Lkg0LzQsNGB0YHQuNCyINGBINCy0LDQu9GO0YLQsNC80Lgg0LTQu9GPINGB0LvQtdC00YPRjtGJ0LXQuSDQuNGC0LXRgNCw0YbQuNC4LAogICAgICAgICAgINC/0L7RgtC+0LzRgyDRh9GC0L4g0YLQtdC60YPRidC40Lkg0LHRg9C00LXRgiDQuNGB0L/QvtC70YzQt9C+0LLQsNGC0YzRgdGPINC00LDQu9GM0YjQtSDQsiBmb3JlYWNoICovCiAgICAgICAgJG5leHRfY3VycmVudF9ub3RlcyA9ICRjdXJyZW50X25vdGVzOwogICAgICAgIAogICAgICAgIC8qINC10YHQu9C4INC60YPQv9GO0YAgPiAwLCDQtNC+0LHQsNCy0LvRj9C10Lwg0LjRhSDQutC+0LvQuNGH0LXRgdGC0LLQviDQuCDQvdC+0LzQuNC90LDQuyDQsiDRgtC10LrRg9GJ0LjQuSDQvdCw0LHQvtGAINCyINC40YLQtdGA0LDRhtC40LggKi8KICAgICAgICBpZigkY3VycmVudF9xdWFudGl0eSkKICAgICAgICAgICAgJG5leHRfY3VycmVudF9ub3Rlc1skbm9taW5hbF0gPSAkY3VycmVudF9xdWFudGl0eTsKCiAgICAgICAgLyog0LXRgdC70Lgg0L7RgdGC0LDRgtC+0Log0YDQsNCy0LXQvSAwIC0g0LTQvtCx0LDQstC70Y/QtdC8INCyINC80LDRgdGB0LjQsiDQstGL0LTQsNGH0LggKi8KICAgICAgICBpZighKCRhbW91bnQgLSAkY3VycmVudF9zdW1tKSl7CiAgICAgICAgICAgICR3aXRoZHJhd1tdID0gJG5leHRfY3VycmVudF9ub3RlczsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgY2hlY2tfd2l0aGRyYXcoJGFtb3VudCAtICRjdXJyZW50X3N1bW0sICRub3RlcywgJG5leHRfY3VycmVudF9ub3Rlcyk7CiAgICB9CgogICAgLyog0L3QsCDQstGL0YXQvtC00LUg0L/QvtC70YPRh9Cw0Y7RgtGB0Y8g0LLRgdC1INCy0L7Qt9C80L7QttC90YvQtSDQutC+0LzQsdC40L3QsNGG0LjQuCDQutGD0L/RjtGALCDQv9GA0Lgg0L7QsdGA0LDQsdC+0YLQutC1INGPINCx0LXRgNGDINC/0LXRgNCy0YPRjiAqLwogICAgcmV0dXJuICR3aXRoZHJhdzsKfQoKZnVuY3Rpb24gZ2V0X21lc3NhZ2UoJHdpdGhkcmF3LCAkYW1vdW50KXsKICAgIGVjaG8gItCh0YPQvNC80LAgJGFtb3VudDpcbiI7CiAgICBpZighZW1wdHkoJHdpdGhkcmF3WzBdKSl7CgogICAgICAgIGVjaG8gItCS0YvQtNCw0YfQsCDQstC+0LfQvNC+0LbQvdCwLCDRh9C40YHQu9C+INC60YPQv9GO0YA6XG4iOwogICAgICAgIGZvcmVhY2goJHdpdGhkcmF3WzBdIGFzICRub21pbmFsID0+ICRxdWFudGl0eSl7CiAgICAgICAgICAgIGVjaG8gJG5vbWluYWwuIngiLiRxdWFudGl0eS4iICI7CiAgICAgICAgfQogICAgfWVsc2V7CiAgICAgICAgZWNobyAi0JLRi9C00LDRh9CwINC90LXQstC+0LfQvNC+0LbQvdCwLiI7CiAgICB9Cn0KCiR3aXRoZHJhdyA9IGNoZWNrX3dpdGhkcmF3KCRhbW91bnQsICRub3Rlc19hdmFpbGFibGUpOwoKZ2V0X21lc3NhZ2UoJHdpdGhkcmF3LCAkYW1vdW50KTs=