<?php

error_reporting(-1);
mb_internal_encoding('utf-8');

$bills = array (
	            500 => 10,
	            1000 => 9,
	            100 => 3,
	            5000 =>5,
	            );
$requiredSum = 16900;

echo "Сумма: $requiredSum. \n";

$cash = 0; // Здесь будем сохранять текущую сумму выдаваемых купюр;

$banknotes = array(); // Здесь все используемые купюры

$limit = 0; //всего денег в банкомате

/* Здесь сохраняем номиналы купюр, которых могло не хватить. 
   Это может потребоваться, а может и нет */
$lackingNotes = array(); 

$err = "Выдача невозможна";
foreach ($bills as $bill => $qty) {
	$limit += $bill*$qty;
}

if ( $limit < $requiredSum ) {
	echo "$err: в банкомате не достаточно средств. \n";
	exit;
}
if ( $requiredSum && ($requiredSum%100) ) {
	echo "$err: введите сумму, кратную 100, 500, 1000 или 5000. \n";
	exit;
}
if ( $requiredSum <= 0 ) {
	echo "$err: минимальная сумма выдачи - 100 (сто) рублей. \n";
	exit;
}
/* 
We may need to sort $bills array in order make sure
that itarations will start from the biggest key. That's how 
we can get as many higher-value banknotes as possible and 
by that minimize overall amount of bills. 
*/
uksort($bills, "compareBills"); 

foreach ($bills as $bill => $qty) {
	$capacity = floor(($requiredSum - $cash)/$bill); 
	if ( ($capacity != 0) && (($requiredSum - $cash)!= 0) && $qty != 0 ) {
		$amount = min($capacity, $qty);
		$cash += $amount * $bill;
		$banknotes[$bill] = $amount;
        if ($capacity > $qty) {
        	$lackingNotes[] = $bill;
        }
	}
}

if ($requiredSum != $cash) {
	$which = end($lackingNotes);
	echo "$err: не достаточно купюр номиналом $which. \n";
	exit;
}
echo "Выдача возможна, число купюр:\n";
foreach ($banknotes as $bill => $qty) {
	echo "{$qty}x{$bill} ";
}
echo "\n";

/*Функция для сортировки */
function compareBills ($a, $b) {
	if ( $a==$b) {
		return 0;
	}
	return ($a>$b) ? -1 : 1;
}