<?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;

PD9waHAKCmVycm9yX3JlcG9ydGluZygtMSk7CgokYW1vdW50ID0gNjIwOwoKJGJpbGxzID0gYXJyYXkoCgkxMCA9PiA1LAoJNTAgPT4gMCwKCTIwMCA9PiAxMCwKCTUwMCA9PiAxMCwKKTsKCiRrZXlzQmlsbHMgPSBhcnJheV9rZXlzKCRiaWxscyk7CgokYXR0ZW1wdHMgPSAwOwoKZnVuY3Rpb24gY291bnRCaWxsc1N1bSgkYmlsbHNDb3B5KSB7CgkKCSR2YWx1ZXNCaWxsc0NvcHkgPSBhcnJheV92YWx1ZXMoJGJpbGxzQ29weSk7Cgkka2V5c0JpbGxzQ29weSA9IGFycmF5X2tleXMoJGJpbGxzQ29weSk7CgkKCWZvcigkaSA9IDA7ICRpIDwgY291bnQoJGJpbGxzQ29weSk7ICRpKyspIHsKCQkkcmVzdWx0WyRpXSA9ICR2YWx1ZXNCaWxsc0NvcHlbJGldICogJGtleXNCaWxsc0NvcHlbJGldOwoJfQkKCSRyZXN1bHQgPSBhcnJheV9zdW0oJHJlc3VsdCk7CglyZXR1cm4gJHJlc3VsdDsJCn0JCgpmdW5jdGlvbiBmaW5kQ2hhbmdlKCRhbW91bnQsICRrZXlzQmlsbHMsICRiaWxscywgJGJpbGxOdW1iZXIsICRsYXN0QW1vdW50KSB7CgkKCSR4ID0gbnVsbDsKCSRkZWJ1Z09mZnNldCA9IHN0cl9yZXBlYXQoIiAgIiwgMyAtICRiaWxsTnVtYmVyKTsKCWVjaG8gInskZGVidWdPZmZzZXR9ZW50ZXIgJGJpbGxOdW1iZXJcbiI7CglnbG9iYWwgJGF0dGVtcHRzOwoJCgkkY3VycmVudEJpbGwgPSAka2V5c0JpbGxzWyRiaWxsTnVtYmVyXTsKCQoJaWYgKCRiaWxsTnVtYmVyID09IDMpIHsKCQllY2hvICLRgdGA0LDQsdC+0YLQsNC70L4iOwoJCSRsYXN0QW1vdW50ID0gJGFtb3VudDsKCX0KCQoJJGN1cnJlbnRNYXhCaWxscyA9IG1pbihmbG9vcigkbGFzdEFtb3VudCAvICRrZXlzQmlsbHNbJGJpbGxOdW1iZXJdKSwgJGJpbGxzWyRjdXJyZW50QmlsbF0pOwoJCglpZiAoJGJpbGxOdW1iZXIgIT0wKSB7CgkJJGxhc3RBbW91bnQgPSAkbGFzdEFtb3VudCAtICRjdXJyZW50QmlsbCokY3VycmVudE1heEJpbGxzOwoJfQoJCglmb3IgKCRpID0gJGN1cnJlbnRNYXhCaWxsczsgJGkgPj0gMDsgJGktLSkgewoJCgkJJGF0dGVtcHRzKys7CgkJJGJpbGxzQ29weSA9ICRiaWxsczsKCQkkYmlsbHNDb3B5WyRjdXJyZW50QmlsbF0gPSAkaTsKCQkkcmVzID0gJGkgKiAkY3VycmVudEJpbGw7CgkJCgkJJHN1bSA9IGNvdW50QmlsbHNTdW0oJGJpbGxzQ29weSk7CgkJZWNobyAieyRkZWJ1Z09mZnNldH0gIGk9JGksIGJpbGxOdW1iZXIgPSAkYmlsbE51bWJlcixsYXN0QW1vdW50ID0gJGxhc3RBbW91bnQsIGJpbGxzICIuaW1wbG9kZSgiLCAiLCAkYmlsbHNDb3B5KS4iLCBzdW09JHN1bVxuIjsKCQkKCQlpZiAoJGJpbGxOdW1iZXIgPiAwKSB7IAoJCQlmaW5kQ2hhbmdlKCRhbW91bnQsICRrZXlzQmlsbHMsICRiaWxsc0NvcHksICRiaWxsTnVtYmVyIC0gMSwgJGxhc3RBbW91bnQpOwoJCQlpZiAoJHgpIHsKCQkJCXJldHVybiAkeDsKCQkJfQoJCX0gZWxzZWlmICgkcmVzID09ICRsYXN0QW1vdW50KSB7CgkJCWVjaG8gInskZGVidWdPZmZzZXR9ICBNQVRDSCAiLmltcGxvZGUoIiwgIiwgYXJyYXlfdmFsdWVzKCRiaWxsc0NvcHkpKS4iIChzdW09JHN1bSlcbiI7CgkJCSR4ID0gaW1wbG9kZSgiLCAiLCBhcnJheV92YWx1ZXMoJGJpbGxzQ29weSkpOwoJCQlyZXR1cm4gJHg7CgkJfSAKCX0KfQoKZWNobyBmaW5kQ2hhbmdlKCRhbW91bnQsICRrZXlzQmlsbHMsICRiaWxscywgMywgJGFtb3VudCk7CmVjaG8gIlxuIi4kYXR0ZW1wdHM7