<?php


header('Content-Type: text/plain; charset=UTF-8');

$amount = 1600;

$bills = array(
    5000    => 2,
    2000    => 1,
    1000    => 1,
    500     => 1,
    200     => 4,
    100     => 0
);

function foo ($amount, $bills, $billUsed=NULL, $result=NULL)
{

    $paid = 0;
    $remain = $amount;
    $k = 0;
    $billKeys = array();
    
    foreach ($bills as $billValue => $billAmount) {

        if ($billValue > $amount || $billAmount == 0 || (isset($billUsed[$billValue]) && $billUsed[$billValue] == TRUE)) {
            continue;
        }

        $billPaymentAmount = floor($remain / $billValue);

        if ($billPaymentAmount == 0) {
            continue;
        }

        if ($billPaymentAmount > $billAmount) {
            $billPaymentAmount = $billAmount;
        }

        $remain -= $billPaymentAmount * $billValue;

        $billUsed[$billValue] = TRUE;
        $billKeys[] = $billValue;
        $k++;

        $result[] = "$billPaymentAmount x $billValue";

    }

    if ($remain != 0) {
        array_pop($result);
        $l = $k - 1;
        $remain += $billKeys[$l];
        foo($remain, $bills, $billUsed, $result);
    }

var_dump($result);
}

foo($amount, $bills);