<?php
header("Content-Type: text/plain");
mb_internal_encoding('utf-8');

/*  Задача про банкомат
 *  пытаемся выдать 6600 р.
 *  число банкнот: 1 по 5000, 4 по 2000, 1 по 500, 3 по 200
 */

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

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

// Номиналы банкнот, количество
$bills = Array (
                1 => Array ('value' => 200, 'quantity' => 3),
                2 => Array ('value' => 500, 'quantity' => 1),
                3 => Array ('value' => 2000, 'quantity' => 4),
                4 => Array ('value' => 5000, 'quantity' => 1)
);
 
// Массив в котором мы храним результат вычислений $results[$numBill][$currentAmount]
$results = array(); 

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

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


// Ф-я считает банкноты для размены требуемой суммы для Анона 
// аргументы: массив с результатом, банкноты (номинал/кол-во), кол-во номиналов, сумма для выдачи, ответ
function findAns($results, $bills, $numBill, $amount, $ans) {
    
    while ($results[$numBill][$amount] != 0) { 
        
        /*  если для размена текущей суммы количество банкнот прошлого номинала нужно столько же,
            то переходим к предыдущему номиналу */
        if ($results[$numBill-1][$amount] == $results[$numBill][$amount]) { 
            $numBill--;
    
        /*  если текущую сумму можно несколько раз выдать текущей банкнотой, делаем это,
            и добавляем текущую банкноту к результату и уменьшаем сумму выдачи на текущий номинал*/
        } elseif ($results[$numBill][$amount] >= $results[$numBill][$amount-$bills[$numBill]['value']]) {
            if (isset($ans[$bills[$numBill]['value']])) {
                $ans[$bills[$numBill]['value']]++;
            } else {
                 $ans[$bills[$numBill]['value']]=1;
            }
            $amount -= $bills[$numBill]['value'];
         
        /*  если остаток текущей суммы, после размена текущей банкнотой, можно выдать только
            банкнотой предыдущего номинала, так тому и быть, + 1 к результату, переходим к
            предыдущему номиналу и уменьшаем сумму выдачи на текущий номинал */   
        } else {  
            if (isset($ans[$bills[$numBill]['value']])) {
                $ans[$bills[$numBill]['value']]++;
            } else {
                 $ans[$bills[$numBill]['value']]=1;
            }
            $numBill--;
            $amount -= $bills[$numBill]['value'];    
        }
    }
    printAns ($ans); // отправляем ответ на печать
}
// Проверяем существует ли ответ для данной суммы, зовем findAns или ругаемся.
function checkAns($results, $bills, $numBill, $amount, $ans) {
    if ($results[$numBill][$amount]==INF) {
        $ans['result']=NULL;
        printAns ($ans); // отправляем ответ на печать
    } else {
        $ans = findAns($results, $bills, $numBill, $amount, $ans);
    }
}

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

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