<?php

error_reporting(-1);

$amount = 620;

$bills = array(
	10 => 5,
	50 => 0,
	200 => 10,
	500 => 10,
);

$keysBills = array_keys($bills);

$attempts = 0;

function countBillsSum($billsCopy) {
	
	$valuesBillsCopy = array_values($billsCopy);
	$keysBillsCopy = array_keys($billsCopy);
	
	for($i = 0; $i < count($billsCopy); $i++) {
		$result[$i] = $valuesBillsCopy[$i] * $keysBillsCopy[$i];
	}	
	$result = array_sum($result);
	return $result;	
}	

function findChange($amount, $keysBills, $bills, $billNumber, $lastAmount) {
	
	$x = null;
	$debugOffset = str_repeat("  ", 3 - $billNumber);
	echo "{$debugOffset}enter $billNumber\n";
	global $attempts;
	
	$currentBill = $keysBills[$billNumber];
	
	if ($billNumber == 3) {
		echo "сработало";
		$lastAmount = $amount;
	}
	
	$currentMaxBills = min(floor($lastAmount / $keysBills[$billNumber]), $bills[$currentBill]);
	
	if ($billNumber !=0) {
		$lastAmount = $lastAmount - $currentBill*$currentMaxBills;
	}
	
	for ($i = $currentMaxBills; $i >= 0; $i--) {
	
		$attempts++;
		$billsCopy = $bills;
		$billsCopy[$currentBill] = $i;
		$res = $i * $currentBill;
		
		$sum = countBillsSum($billsCopy);
		echo "{$debugOffset}  i=$i, billNumber = $billNumber,lastAmount = $lastAmount, bills ".implode(", ", $billsCopy).", sum=$sum\n";
		
		if ($billNumber > 0) { 
			findChange($amount, $keysBills, $billsCopy, $billNumber - 1, $lastAmount);
			if ($x) {
				return $x;
			}
		} elseif ($res == $lastAmount) {
			echo "{$debugOffset}  MATCH ".implode(", ", array_values($billsCopy))." (sum=$sum)\n";
			$x = implode(", ", array_values($billsCopy));
			return $x;
		} 
	}
}

echo findChange($amount, $keysBills, $bills, 3, $amount);
echo "\n".$attempts;