<?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}";
}