<?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++;	
			}
		}
		
		$i = count($banknotes);
		$result = array_fill_keys(array_keys($banknotes), 0);
		$amount = $amountSave;
		krsort($banknotes, SORT_NUMERIC);
		while($amount>0){
			foreach ($banknotes as $key => $value) {
				while((($result[$key]+1) <= $banknotes[$key]) & ($amount-$key)>=0){
					if ($minBanknotes[$i][$amount-$key] == $minBanknotes[$i][$amount]-1){
						$result[$key]++;
						$amount -= $key;
					}else{
						echo $amount."\n";
						print_r($result);
						exit("Неверный путь");
					}
				}
				$i--;
				if($i<0){
					exit("Все пошло по пизде");
				}
			}
		}

		$resultStr = "";
		foreach ($result as $key => $value) {
			if($value != 0){
				$resultStr = $resultStr."{$value}x{$key} ";
			}
		}
		
		echo $resultStr."\n";
	}
	
	
	$amount = 34;
	
	$banknotes = array (
		2 => 3,
		5 => 10,
		10 => 1
	);

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