<?php
mb_internal_encoding('utf-8');

// Банкомат

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

// Ответ:  сумма размены "0" => "$amount", номиналы и их количество "bill" => "count"
$ans = array ($amount); 

// Номиналы банкнот, количество
$bills = Array (
                1 => Array (200, 3),
                2 => Array (500, 1),
                3 => Array (2000, 4),
                4 => Array (5000, 1)
);
 
$INF=1000000;           // Значение константы
$Results[$i][$m];       // Массив в котором мы храним результат

// Для всех сумм банкнотой 0 размен не ввозможен
for ($i = 0; $i<=$amount    ; $i++) {    
    $Results[0][$i] = $INF;}
    
// Если просят разменять сумму 0, гордо протягиваем пустую ладонь.
for ($i = 0; $i<=4; $i++) {    
    $Results[$i][0] = 0;
}

// m - сумма, которую нужно выдать, увеличиваем сумму от 1 до требуемой $amount
for($m=1; $m<=$amount; $m++) {
    
    // Перебираем все номиналы банкнот
    foreach ($bills as $i => $value) {
        
        // По умолчанию, текущую сумму можно выдать банкнотой предыдущего номинала.                       
        $Results[$i][$m] =  $Results[$i-1][$m];
        
        // Есть ли банкноты текущего номинала и текущую сумму можно разменять текущим номиналом           
        if ($value[1]>0 && $m>= $value[0]) {
            
            /*  Перебераем количество банкнот текущего номинала
                от минимально требуемого (или того что есть) до 1 */
            for ($l=min($value[1], intval(floor($m/$value[0]))); $l>=1; $l--) {
                
                /*  Выбираем минимальное количество банкнот для размена между данной банкнотой и предыдущей
                    если сумму меняем текущей банкнотой, то записываем количество банкнот
                    для данного номинала и количество монет предыдущих номиналов, для размена остатка суммы  */
                $Results[$i][$m] =  min($Results[$i][$m], $Results[$i-1][$m - $l * $value[0]] + $l); 
            }
        }
    }
}   

// Рекурсивная Няша, считает банкноты для размены требуемой суммы для Анона
// аргументы: массив с результатом, банкноты (номинал/кол-во),  кол-во номиналов, сумма для выдачи
function findAnsRecur($Results, $bills, $i, $amount, $ans) {
    
    if ($Results[$i][$amount] == 0) { // финиш
        printAns ($ans);
    
    /*  если для размена текущей суммы количество банкнот прошлого номинала нужно столько же,
        то переходим к предыдущему номиналу */
    } elseif ($Results[$i-1][$amount] == $Results[$i][$amount]) { 
        $i--;
        findAnsRecur($Results, $bills, $i, $amount, $ans);

    /*  если текущую сумму можно несколько раз выдать текущей банкнотой, делаем это,
        и добавляем текущую банкноту к результату и уменьшаем сумму выдачи на текущий номинал*/
    } elseif ($Results[$i][$amount] >= $Results[$i][$amount-$bills[$i][0]]) {
        $ans[$bills[$i][0]]++; 
        $amount -= $bills[$i][0];
        findAnsRecur($Results, $bills, $i, $amount, $ans);
     
    /*  если остаток текущей суммы, после размена текущей банкнотой, можно выдать только
        банкнотой предыдущего номинала, так тому и быть, + 1 к результату, переходим к
        предыдущему номиналу и уменьшаем сумму выдачи на текущий номинал */   
    } else {  
        //$ans[] = $bills[$i][0];
        $ans[$bills[$i][0]]++;
        $i--;
        $amount -= $bills[$i][0];    
        findAnsRecur($Results, $bills, $i, $amount, $ans);  
    }
}
// Проверяем существует ли ответ для данной суммы, зовем рекурсивную Няшу или ругаемся.
function checkAns($Results, $bills, $i, $amount, $ans) {
    if ($Results[$i][$amount]==$INF) {
        $ans=NULL;      
    } else {
        $ans = findAnsRecur($Results, $bills, $i, $amount, $ans);
    }
}

// Выводим результат
function printAns ($ans) {
    
    echo "Сумма: {$ans[0]}\n";
    
    if ($ans==NULL) {
        echo "Требуемую сумму выдать невозможно";
    } else {
        echo "Выдача возможна, число купюр:\n";
        
        foreach($ans as $bill=>$count) {
            if ($bill!=0) {
                echo "{$count}x{$bill}" . " ";
            }
        }
    }
}

// Запускаем проверку
checkAns($Results, $bills, count($bills), $amount, $ans) ;

?>