<?php

$amount = 56000;

$bills = [
    100  => 23,
    500  => 5,
    1000 => 0,
    5000 => 10
];

echo "Сумма: $amount\n";

if ($amount <= 0) echo "Выдача невозможна, сумма слишком мала\n";

$remainder = $amount % key($bills);
if ($remainder != 0) echo "Выдача невозможна, нет купюр чтобы выдать $remainder\n";

krsort($bills);

echo "Купюр в банкомате:\n";
print_r($bills);

$output = '';
$change_possible = false;
$ret = change($amount, $bills, $bills, $output, $change_possible);

if ($change_possible) echo "Выдача возможна: $output\n";
else echo "Выдача невозможна, в банкомате не хватает денег чтобы выдать $ret\n";

echo "Купюр в банкомате:\n";
print_r($ret);

function change($amount, $bills, $new_bills, &$output, &$change_possible) {

    if (count($bills) <= 0) { // Купюры кончились

        if ($amount > 0) { // Купюры кончились, но ещё не вся сумма выдана
            $change_possible = false;
            return $amount;
        } else { // Купюры кончились и вся сумма выдана
            return $new_bills;
        }
    }

    $bill_count = reset($bills);    // Количество купюр номинала
    $bill_value = key($bills);      // Номинал купюр
    unset($bills[$bill_value]);

    // Если купюры данного номинала закончились
    if ($bill_count == 0) return change($amount, $bills, $new_bills, $output, $change_possible);

    $whole = intdiv($amount, $bill_value);

    if ($whole > 0) { // Чё-то можем выдать купюрами данного номинала

        // Нельзя выдать больше купюр, чем есть
        if ($whole > $bill_count) $whole = $bill_count;

        $new_bills[$bill_value] -= $whole;
        $amount -= $whole * $bill_value;

        $output .= "{$whole}x{$bill_value} ";

        $change_possible = true;
        return change($amount, $bills, $new_bills, $output, $change_possible);

    } else { // Ниче не можем выдать купюрами данного номинала

        $remainder = $amount % $bill_value;

        return change($remainder, $bills, $new_bills, $output, $change_possible);
    }
}