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

PD9waHAKCiRhbW91bnQgPSA0MjcwMDsKZWNobyAn0KHRg9C80LzQsDogJy4gJGFtb3VudC4gIlxuIjsKJGZpbmFsQ291bnQgPSBhcnJheSgpOyAvL9Cc0LDRgdGB0LjQsiDQtNC70Y8g0LLRi9Cy0L7QtNCwINC+0L/RgtC40LzQsNC70YzQvdC+0LPQviDQutC+0Lst0LLQsCDQutGD0L/RjtGAINC00LvRjyDRgNCw0LfQvNC10L3QsAokbnVtT2ZCYW5rbm90ZXMgPSBhcnJheSgpOyAvL9Cc0LDRgdGB0LjQsiDQtNC70Y8g0LLRi9Cy0L7QtNCwINC60L7Quy3QstCwINC60LDQttC00L7Qs9C+INC90L7QvNC40L3QsNC70LAg0LrRg9C/0Y7RgAokZmluYWxDb3VudFswXSA9IDA7CgokYmFua25vdGVBcnJheSA9IGFycmF5KAoJMTAwCQk9PgkxMCwKCTUwMAkJPT4JMTAsCgkxMDAwCT0+CTEwLAoJNTAwMAk9PgkxMAopOwoKZm9yKCRpID0gMTAwOyAkaSA8PSAkYW1vdW50OyAkaSs9IDEwMCl7IC8v0JfQsNC/0L7Qu9C90Y/QtdC8INC80LDRgdGB0LjQsiAkZmluYWxDb3VudAoJJGZpbmFsQ291bnRbJGldID0gUEhQX0lOVF9NQVg7IC8vJGkgLSDQodGD0LzQvNCwLCDQutC+0YLQvtGA0YPRjiDQvdGD0LbQvdC+INCy0YvQtNCw0YLRjC4g0J/QvtC80LXRh9Cw0Y4g0YfRgtC+INC10LUg0L/QvtC60LAg0L3QtdC70YzQt9GPINCy0YvQtNCw0YLRjAoJZm9yZWFjaCgkYmFua25vdGVBcnJheSBhcyAka2V5ID0+ICR2YWx1ZSl7IC8v0J/QtdGA0LXQsdC40YDQsNGOINCy0YHQtSDQvdC+0LzQuNC90LDQu9GLINCx0LDQvdC60L3QvtGCCgkJaWYoJGtleSA8PSAkaSAmJiAkZmluYWxDb3VudFskaSAtICRrZXldICsgMTAwIDwgJGZpbmFsQ291bnRbJGldKXsKCQkJJGZpbmFsQ291bnRbJGldID0gJGZpbmFsQ291bnRbJGkgLSAka2V5XSArIDEwMDsgLy/QmNC30LzQtdC90Y/RjiDQt9C90LDRh9C10L3QuNC1ICRmaW5hbENvdW50WyRpXSDQtdGB0LvQuCDQvdCw0YjQtdC7INC70YPRh9GI0LXQtSDRgNC10YjQtdC90LjQtQoJCX0KCX0KfQppZigkZmluYWxDb3VudFskYW1vdW50XSA9PSBQSFBfSU5UX01BWCl7CgllY2hvICLQlNCw0L3QvdGD0Y4g0YHRg9C80LzRgyDQstGL0LLQtdGB0YLQuCDQvdC10LLQvtC30LzQvtC20L3QvlxuIjsKfWVsc2V7Cgl3aGlsZSgkYW1vdW50ID4gMCl7IC8v0J/QvtC60LAg0YHRg9C80LzQsCDQstGL0YjQtSDQvdGD0LvRjyDQv9GA0L7QtNC+0LvQttCw0LXQvCDQv9GA0L7Qs9C+0L3Rj9GC0Ywg0LzQsNGB0YHQuNCyINC/0L4g0LrRgNGD0LPRgwoJCWZvcmVhY2goJGJhbmtub3RlQXJyYXkgYXMgJGtleSA9PiAkdmFsdWUpewoJCQlpZigkZmluYWxDb3VudFskYW1vdW50IC0gJGtleV0gPT0gJGZpbmFsQ291bnRbJGFtb3VudF0gLSAxMDApeyAvL9CV0YHQu9C4INC00LvRjyDQutCw0LrQvtCz0L4t0YLQviBpINC+0LrQsNC20LXRgtGB0Y8sINGH0YLQviBGKG4gLSBhaSkgPSBGKG4pIC0gMSwg0LfQvdCw0YfQuNGCLCDQvNGLINC80L7QttC10Lwg0LLRi9C00LDRgtGMINCx0LDQvdC60L3QvtGC0YMg0LIgJGtleSDRgNGD0LHQu9C10LkKCQkJCSRudW1PZkJhbmtub3Rlc1tdID0gJGtleTsKCQkJCSRhbW91bnQtPSAka2V5OwoJCQkJYnJlYWs7CgkJCX0KCQl9Cgl9Cn0KJHB1cmVOdW1PZkJhbmtub3RlcyA9IGFycmF5X2NvdW50X3ZhbHVlcygkbnVtT2ZCYW5rbm90ZXMpOyAvL9Ch0YfQuNGC0LDQtdC8INC60L7Quy3QstC+INC60YPQv9GO0YAg0LrQsNC20LTQvtCz0L4g0L3QvtC80LjQvdCw0LvQsAplY2hvICLQktGL0LTQsNGH0LAg0LLQvtC30LzQvtC20L3QsCwg0YfQuNGB0LvQviDQutGD0L/RjtGAOlxuIjsKZm9yZWFjaCgkcHVyZU51bU9mQmFua25vdGVzIGFzICRub21pbmFsPT4kcmVwZWF0KXsKCWVjaG8gInskbm9taW5hbH14eyRyZXBlYXR9ICI7Cn0=