<?php

$amount = 42700;
echo 'Сумма: '. $amount. "\n";
$finalCount = array(); //Массив для вывода оптимального кол-ва купюр для размена
$numOfBanknotes = array(); //Массив для вывода кол-ва каждого номинала купюр
$finalCount[0] = 0;

$banknoteArray = array(
	100		=>	10,
	500		=>	10,
	1000	=>	10,
	5000	=>	10
);

for($i = 100; $i <= $amount; $i+= 100){ //Заполняем массив $finalCount
	$finalCount[$i] = PHP_INT_MAX; //$i - Сумма, которую нужно выдать. Помечаю что ее пока нельзя выдать
	foreach($banknoteArray as $key => $value){ //Перебираю все номиналы банкнот
		if($key <= $i && $finalCount[$i - $key] + 100 < $finalCount[$i]){
			$finalCount[$i] = $finalCount[$i - $key] + 100; //Изменяю значение $finalCount[$i] если нашел лучшее решение
		}
	}
}
if($finalCount[$amount] == PHP_INT_MAX){
	echo "Данную сумму вывести невозможно\n";
}else{
	while($amount > 0){ //Пока сумма выше нуля продолжаем прогонять массив по кругу
		foreach($banknoteArray as $key => $value){
			if($finalCount[$amount - $key] == $finalCount[$amount] - 100){ //Если для какого-то i окажется, что F(n - ai) = F(n) - 1, значит, мы можем выдать банкноту в $key рублей
				$numOfBanknotes[] = $key;
				$amount-= $key;
				break;
			}
		}
	}
}
$pureNumOfBanknotes = array_count_values($numOfBanknotes); //Считаем кол-во купюр каждого номинала
echo "Выдача возможна, число купюр:\n";
foreach($pureNumOfBanknotes as $nominal=>$repeat){
	echo "{$nominal}x{$repeat} ";
}