<?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);

$amount2 = 600;
$withdraw = check_withdraw($amount2, $notes_available);
get_message($withdraw, $amount2);