<?php
 
$bills = [
	5000 => 1,
	2000 => 4,
	500 => 1,
	200 => 3
];
$sum = 6600;
$result = [];
 
/** Возвращает массив банкнот в формате $номинал => $количество */
function getBillsAndAmount($sum, $bills, &$result, $pastResult = []) {
 
	foreach ($bills as $bill => $amount) {
		// Заведем временные переменные, дублирующие переданные в параметры ф-ции данные
		$tempSum = $sum;
		$tempBills = $bills;
		$tempResult = $pastResult;
 
		if ($bill <= $sum && $amount > 0) {
			// Определим сколько нам нужно купюр данного номинала для указанной суммы
			$requiredAmount = floor($tempSum / $bill);
 
			// Если купюр номинала не хватает, приравниваем нужное количество к существующему
			if ($requiredAmount > $amount) $requiredAmount = $amount;
 
			// Обновим временные переменные
			$tempResult[$bill] = $requiredAmount;
			$tempBills[$bill] -= $requiredAmount;
			$tempSum -= $bill * $requiredAmount;
 
			// Посчитаем сумму купюр остальных номиналов
			$amountOfBills = 0;
			foreach ($tempBills as $bill2 => $amount2) {
				if ($bill2 < $bill) {
	            	$amountOfBills += $bill2 * $amount2;
	        	}
			}
 
			// Повторяется, пока хватает суммы остальных номиналов
			while ($requiredAmount > 0 && $amountOfBills >= $tempSum) {
				// Если есть остаток - рекурсируем функцию
				if ($tempSum > 0) {
					getBillsAndAmount($tempSum, $tempBills, $result, $tempResult);
				} else {
					$result = $tempResult;
					break;
				}
 
				$requiredAmount--;
			}
 
		}
 
	}
 
}
 
getBillsAndAmount($sum, $bills, $result);
 
if ($result) {
	echo "Сумма: $sum\n";
	echo "Выдача возможна, число купюр:\n";
	foreach ($result as $bill => $amount) {
		echo "{$bill}x{$amount} ";
	}
} else {
	echo "Выдача невозможна: не хватает купюр.";
}

PD9waHAKCiRiaWxscyA9IFsKCTUwMDAgPT4gMSwKCTIwMDAgPT4gNCwKCTUwMCA9PiAxLAoJMjAwID0+IDMKXTsKJHN1bSA9IDY2MDA7CiRyZXN1bHQgPSBbXTsKCi8qKiDQktC+0LfQstGA0LDRidCw0LXRgiDQvNCw0YHRgdC40LIg0LHQsNC90LrQvdC+0YIg0LIg0YTQvtGA0LzQsNGC0LUgJNC90L7QvNC40L3QsNC7ID0+ICTQutC+0LvQuNGH0LXRgdGC0LLQviAqLwpmdW5jdGlvbiBnZXRCaWxsc0FuZEFtb3VudCgkc3VtLCAkYmlsbHMsICYkcmVzdWx0LCAkcGFzdFJlc3VsdCA9IFtdKSB7CgkKCWZvcmVhY2ggKCRiaWxscyBhcyAkYmlsbCA9PiAkYW1vdW50KSB7CgkJLy8g0JfQsNCy0LXQtNC10Lwg0LLRgNC10LzQtdC90L3Ri9C1INC/0LXRgNC10LzQtdC90L3Ri9C1LCDQtNGD0LHQu9C40YDRg9GO0YnQuNC1INC/0LXRgNC10LTQsNC90L3Ri9C1INCyINC/0LDRgNCw0LzQtdGC0YDRiyDRhC3RhtC40Lgg0LTQsNC90L3Ri9C1CgkJJHRlbXBTdW0gPSAkc3VtOwoJCSR0ZW1wQmlsbHMgPSAkYmlsbHM7CgkJJHRlbXBSZXN1bHQgPSAkcGFzdFJlc3VsdDsKCQkKCQlpZiAoJGJpbGwgPD0gJHN1bSAmJiAkYW1vdW50ID4gMCkgewoJCQkvLyDQntC/0YDQtdC00LXQu9C40Lwg0YHQutC+0LvRjNC60L4g0L3QsNC8INC90YPQttC90L4g0LrRg9C/0Y7RgCDQtNCw0L3QvdC+0LPQviDQvdC+0LzQuNC90LDQu9CwINC00LvRjyDRg9C60LDQt9Cw0L3QvdC+0Lkg0YHRg9C80LzRiwoJCQkkcmVxdWlyZWRBbW91bnQgPSBmbG9vcigkdGVtcFN1bSAvICRiaWxsKTsKCQkJCgkJCS8vINCV0YHQu9C4INC60YPQv9GO0YAg0L3QvtC80LjQvdCw0LvQsCDQvdC1INGF0LLQsNGC0LDQtdGCLCDQv9GA0LjRgNCw0LLQvdC40LLQsNC10Lwg0L3Rg9C20L3QvtC1INC60L7Qu9C40YfQtdGB0YLQstC+INC6INGB0YPRidC10YHRgtCy0YPRjtGJ0LXQvNGDCgkJCWlmICgkcmVxdWlyZWRBbW91bnQgPiAkYW1vdW50KSAkcmVxdWlyZWRBbW91bnQgPSAkYW1vdW50OwoJCQkKCQkJLy8g0J7QsdC90L7QstC40Lwg0LLRgNC10LzQtdC90L3Ri9C1INC/0LXRgNC10LzQtdC90L3Ri9C1CgkJCSR0ZW1wUmVzdWx0WyRiaWxsXSA9ICRyZXF1aXJlZEFtb3VudDsKCQkJJHRlbXBCaWxsc1skYmlsbF0gLT0gJHJlcXVpcmVkQW1vdW50OwoJCQkkdGVtcFN1bSAtPSAkYmlsbCAqICRyZXF1aXJlZEFtb3VudDsKCQkJCgkJCS8vINCf0L7RgdGH0LjRgtCw0LXQvCDRgdGD0LzQvNGDINC60YPQv9GO0YAg0L7RgdGC0LDQu9GM0L3Ri9GFINC90L7QvNC40L3QsNC70L7QsgoJCQkkYW1vdW50T2ZCaWxscyA9IDA7CgkJCWZvcmVhY2ggKCR0ZW1wQmlsbHMgYXMgJGJpbGwyID0+ICRhbW91bnQyKSB7CgkJCQlpZiAoJGJpbGwyIDwgJGJpbGwpIHsKCSAgICAgICAgICAgIAkkYW1vdW50T2ZCaWxscyArPSAkYmlsbDIgKiAkYW1vdW50MjsKCSAgICAgICAgCX0KCQkJfQoJCQkKCQkJLy8g0J/QvtCy0YLQvtGA0Y/QtdGC0YHRjywg0L/QvtC60LAg0YXQstCw0YLQsNC10YIg0YHRg9C80LzRiyDQvtGB0YLQsNC70YzQvdGL0YUg0L3QvtC80LjQvdCw0LvQvtCyCgkJCXdoaWxlICgkcmVxdWlyZWRBbW91bnQgPiAwICYmICRhbW91bnRPZkJpbGxzID49ICR0ZW1wU3VtKSB7CgkJCQkvLyDQldGB0LvQuCDQtdGB0YLRjCDQvtGB0YLQsNGC0L7QuiAtINGA0LXQutGD0YDRgdC40YDRg9C10Lwg0YTRg9C90LrRhtC40Y4KCQkJCWlmICgkdGVtcFN1bSA+IDApIHsKCQkJCQlnZXRCaWxsc0FuZEFtb3VudCgkdGVtcFN1bSwgJHRlbXBCaWxscywgJHJlc3VsdCwgJHRlbXBSZXN1bHQpOwoJCQkJfSBlbHNlIHsKCQkJCQkkcmVzdWx0ID0gJHRlbXBSZXN1bHQ7CgkJCQkJYnJlYWs7CgkJCQl9CgkJCQkKCQkJCSRyZXF1aXJlZEFtb3VudC0tOwoJCQl9CgkJCQoJCX0KCQkKCX0KCQp9CgpnZXRCaWxsc0FuZEFtb3VudCgkc3VtLCAkYmlsbHMsICRyZXN1bHQpOwoKaWYgKCRyZXN1bHQpIHsKCWVjaG8gItCh0YPQvNC80LA6ICRzdW1cbiI7CgllY2hvICLQktGL0LTQsNGH0LAg0LLQvtC30LzQvtC20L3QsCwg0YfQuNGB0LvQviDQutGD0L/RjtGAOlxuIjsKCWZvcmVhY2ggKCRyZXN1bHQgYXMgJGJpbGwgPT4gJGFtb3VudCkgewoJCWVjaG8gInskYmlsbH14eyRhbW91bnR9ICI7Cgl9Cn0gZWxzZSB7CgllY2hvICLQktGL0LTQsNGH0LAg0L3QtdCy0L7Qt9C80L7QttC90LA6INC90LUg0YXQstCw0YLQsNC10YIg0LrRg9C/0Y7RgC4iOwp9