<?php
	// Staring straight up into the sky ... oh my my
	error_reporting(-1);
	mb_internal_encoding('utf-8');

	function calculateDelivery(&$banknotes, $amount){
		ksort($banknotes);
		
		$amountSave = $amount;
		$INF = 1000000000;
		$minBanknotes = array();
		$minBanknotes[0][0] = 0;
		
		for($m=0; $m<=$amount; $m++){
			$minBanknotes[0][$m] = $m==0?0:$INF;
			$p=1;
			foreach ($banknotes as $key => $value) {
				if($m <= $key-1){
					$minBanknotes[$p][$m] = $minBanknotes[$p-1][$m];
				}else{
					$minBanknotes[$p][$m] = min($minBanknotes[$p-1][$m], $minBanknotes[$p][$m-$key] + 1);
				}
				$p++;	
			}
		}
		
		for($i=count($banknotes);$i>=1;$i--){
			$result = array_fill_keys(array_keys($banknotes), 0);
			$amount = $amountSave;
			
			if ($minBanknotes[$i][$amount]==$INF){
				exit("Данным набором банкнот сумму выдать невозможно");
			}else{
				while($amount>0){
					foreach ($minBanknotes[$i] as $key => $value) {
						if ($minBanknotes[$i][$amount-$key] == $minBanknotes[$i][$amount]-1){
							$result[$key]++;
							$amount -= $key;
							break;
						}
					}
				}
			}
			
			$resultStr = "";
			foreach ($result as $key => $value) {
				if($value != 0){
					$resultStr = $resultStr."{$value}x{$key} ";
				}
			}
			echo $resultStr."\n";			
		}
	}
	
	$amount = 66;
	
	$banknotes = array (
		2 => 3,
		5 => 1,
		20 => 4,
		50 => 1
	);

	echo "Сумма: {$amount}\n";
	calculateDelivery($banknotes, $amount);
?>