<?php //задача банкомата

error_reporting(-1);

$listOfBill = array(100,200,500,1000,2000,5000);
$countOfBill = array(80,40,20,10,10,10);

$demand = 9400;
$billCountLimit = 6;						//максимальное количество купюр в выдаче

function calculateSumOfBill($countBill,$listOfBill){
	$sum = 0;
	for ($i=0;$i<count($listOfBill);$i++){
		$sum += $countBill[$i]*$listOfBill[$i]; 
	}
	return $sum;
}
function returnListOfBill($countBill,$listOfBill){
	$str = "";
	for ($i=0;$i<count($listOfBill);$i++){
		if ($countBill[$i]!=0){
			$str = $str." ".$countBill[$i]." по ".$listOfBill[$i]; 
		}
	}
	return $str;
}	
$result = array();
$resultListOfBill = array();
$n = 1;
$key = 0;
$billCount = 0;
$reason = "Недостаточно купюр!";
$resultListOfBill = array(array(0,0,0,0,0,0));
while ($n<1000000){
	$k = 0;
	$resultList = array();
	for ($j=0;$j<$n;$j++) {								//Цикл по вариантам выдачи
		for ($i=0;$i<count($listOfBill);$i++) {			//Цикл по типам купюр
			$resultList[$k] = $resultListOfBill[$j]; 
			if ($resultList[$k][$i]<$countOfBill[$i]){ 	//проверка на наличие купюры
				$resultList[$k][$i] += 1; 
				$intermediateResult = calculateSumOfBill($resultList[$k],$listOfBill);
				if ($intermediateResult<$demand){				//Проверка суммы выдачи, если меньше трбуемого оставляем этот набор купюр			
					$k++;	
				}
				elseif($intermediateResult==$demand){			//если достаточно, завершаем поиск
					$result = $resultList[$k];
					$key = 1;
					break;
				}
				else{											//если больше, удаляем этот набор 
				//echo "Номер $j удалён.\n";
				}
			}
		}
		if ($key==1){
			break;
		}
	}
	if ($key==1){
		break;
	}
	$billCount++;
	$resultListOfBill = $resultList;
	$n = count($resultListOfBill);
	if ($n<2){
		$reason = "Невозможно выдать нужную сумму этим набором купюр!";
		break;
	}
	if ($billCount>$billCountLimit){
		$reason = "Слишком много купюр выдавать, банкомату лень!";
		break;
	}
}
echo "Требуемая сумма: $demand\n";
if ($key) { 
	$a = returnListOfBill($result,$listOfBill);
	echo "Выдача возможна: $a \n";
	}
else  { 
	echo "Выдача невозможна: $reason \n"; 
}