<?php

error_reporting(-1);

//требуемая сумма
$amount = 6600;

//запас наличных 
$nominals = array(100, 200, 500, 1000, 2000, 5000);
$check = array();
$check[0] = array(
   100      =>   0,
   200      =>   3,
   500      =>   1,
   1000     =>   0,
   2000     =>   4,
   5000     =>   1
);

/*  Алгоритм начинает свою работу с того что массив $solutionsStorage заполняется значением 9999
значение 9999 в данном случае аналог false. Ключ в данном массиве - число, для которого ищется лучшее (меньшее) количество банкнот, которым можно выдать это число.
Значение массива $solutionsStorage под ключём n - лучшее(меньшее) количество банкнот, которым можно выдать  число n.
Значению $solutionsStorage с ключём 0 присваиваится целочисленное значение 0, так как сумму 0р можно выдать количеством 0 банкнот.

Далее цикл перебирает массив $solutionsStorage, и для каждого ключа(и каждого значения $amount до 6600 соответственно) находит лучшее(меньшее количество банкнот) алгоритмом описанным ниже.
Если же определённую сумму выдать нельзя, то у ключа равного этой сумме значение будет 9999 - то есть false.
Чтобы лучше понять как действует алгоритм рассмотрим его работу поэтапно на примере суммы 100 р и 500р. 

$k = 100 (рассматривается ситуация, когда в банкомате есть купюра в 100р, в рабочем примере этой купюры в банкомате нет)
строка 75: банкнота номиналом 100(все остальные банкноты не проходят первую проверку в строке 76)
строка 76: $solutionsStorage[100 - 100] < $solutionsStorage[100](тут будет число 9999 в первом проходе цикла)
вторая проверка в строке 76 нужна для двух целей. Первая цель - определить что данную сумму вообще возможно выдать
имеющимися номиналами (если нельзя, то $solutionsStorage[$k - $nominals[$i]] будет больше или равно $solutionsStorage[$k]
Вторая цель - определить минимальное количество банкнот, которым можно выдать сумму(более подробно будет рассмотренно
в примере с суммой в 500р))
строка 76: третья проверка определяет есть ли нужная купюра номиналом $i в банкомате
строка 77: если все три проверки успешны, значению $solutionsStorage[100] присваивается значение $solutionsStorage[0]
строка 78: также значению $check[100] присваивается массив с количеством доступных банкнот, который находится в $check[0]
строка 79: также в переменную $bestNominal записывается номинал банкноты - 100, также переменная $tic становится true
далее, если все три проверки пройдены, и найден лучший номинал для суммы $k мы отнимаем 1 банкноту номинала $bestNominal
из массива с количеством доступных банкнот(строка 85), добавляем одну банкноту к истинному решению в массив $solutionsStorage с ключем 100 (строка 86)
таким образом значение $solutionsStorage[100] становится 1, и в заключении задаем переменной $tic значение false\

$k = 500 (рассматривается ситуация, когда в банкомате есть купюра в 100р, в рабочем примере этой купюры в банкомате нет)
Первая итерация вложенного цикла{
В этот раз я не буду акцентировать внимание на первой проверке, сразу перейдём ко второй
строка 75: банкнота номиналом 100р
строка 76: $solutionsStorage[500 - 100](под этим ключем будет значение 2 банкноты, высчитанное ранее, 2 меньше чем 9999)
строка 76: купюра с номиналом $nominals[$i] , то есть 100 в массиве с количеством доступных банкнот у нас тоже есть, значит третью проверку мы проходим
далее присваиваем $solutionsStorage[500] значение 2 (купюры), прибавляем к этому значению 1, и вычитаем одну купюру этого номинала из
банкомата, массив который представляет это теперь находится в $check[500]
}
Вторая итерация вложенного цикла{
строка 75: банкнота номиналом 200р
строка 76: $solutionsStorage[500 - 200](под этим ключем будет значение 2 банкноты, высчитанное ранее, 2  меньше чем 3, вторая проверка пройдена)
Дальше идут примерно те же действия что и в первой итерации, с небольшими различиями (так, например значение $check[500] заполняется значением $check[300]
вместо $check[400], и уже оттуда вычитается одна банкнота номиналом 200р)
}
Третья итерация вложенного цикла{
строка 75: банкнота номиналом 500р
строка 76: $solutionsStorage[500 - 500](под этим ключем будет значение 0 банкноты, высчитанное ранее, 0  меньше чем 3, вторая проверка пройдена)
После выполняются те же действия что и в итерациях выше с небольшими различиями.
}
В итоге в $solutionsStorage[500] значение 1 (одна банкнота), а из $check[500] будет вычтена 1 банкнота номиналом 500р
*/

$tic = false; //переменная, которая позволяет или запрещает добавить одну банкноту к истинному решению, в зависимости от истинности выражения в строке 
$bestNominal = 0;
$solutionsStorage  = array();
$solutionsStorage = array_fill(0, $amount + 1, 9999); // заполнение массива значением 9999, до $amount
$solutionsStorage[0] = 0;
for ($k = 1; $k < $amount + 1; $k++){
	for ($i = 0; $i < count($nominals); $i++){
		if ($k - $nominals[$i] >= 0 && $solutionsStorage[$k - $nominals[$i]] < $solutionsStorage[$k] && $check[$k - $nominals[$i]][$nominals[$i]] > 0){
			$solutionsStorage[$k] = $solutionsStorage[$k - $nominals[$i]];
			$check[$k] = $check[$k - $nominals[$i]]; //присвоение массиву в значении $k массива ($k - номинал банкноты)
			$bestNominal = $nominals[$i];
			$tic = true;
		}
		
	}
	if($tic == true){       //прибавление банкноты к истинному решению, вычитание банкноты из банкомата
	$check[$k][$bestNominal] -= 1; 
    $solutionsStorage[$k] += 1;
	$tic = false;
	}
}

if ($solutionsStorage[$amount] >= 9999){
	echo 'выдать сумму невозможно';
}
else{
	if ($solutionsStorage[$amount] == 0){
	'выдано ноль банкнот';
    }
    else{
	echo "Сумма к выдаче:{$amount}\n";
	echo "выдано банкнот всего: {$solutionsStorage[$amount]}\n";
    for($p = count($nominals) - 1; $p >= 0; $p--){
		$bankn = $check[0][$nominals[$p]] - $check[$amount][$nominals[$p]];
		echo "выдано {$bankn} банкнот номиналом {$nominals[$p]} рублей\n";
	    } 
    }
}