fork download
copy 
  1. <?php
  2. 	// Staring straight up into the sky ... oh my my
  3. 	error_reporting(-1);
  4. 	mb_internal_encoding('utf-8');
  5.  
  6. 	function calculateDelivery(&$banknotes, $amount){
  7. 		ksort($banknotes);
  8. 		$amountSave = $amount;
  9. 		$INF = 1000000000;
  10. 		$minBanknotes = array();
  11. 		$minBanknotes[0][0] = 0;
  12.  
  13. 		for($m=0; $m<=$amount; $m++){
  14. 			$minBanknotes[0][$m] = $m==0?0:$INF;
  15. 			$p=1;
  16. 			foreach ($banknotes as $key => $value) {
  17. 				if($m <= $key-1){
  18. 					$minBanknotes[$p][$m] = $minBanknotes[$p-1][$m];
  19. 				}else{
  20. 					$minBanknotes[$p][$m] = min($minBanknotes[$p-1][$m], $minBanknotes[$p][$m-$key] + 1);
  21. 				}
  22. 				$p++;	
  23. 			}
  24. 		}
  25.  
  26. 		$i = count($banknotes);
  27. 		$result = array_fill_keys(array_keys($banknotes), 0);
  28. 		$amount = $amountSave;
  29. 		krsort($banknotes, SORT_NUMERIC);
  30. 		while($amount>0){
  31. 			foreach ($banknotes as $key => $value) {
  32. 				while((($result[$key]+1) <= $banknotes[$key]) & ($amount-$key)>=0){
  33. 					if ($minBanknotes[$i][$amount-$key] == $minBanknotes[$i][$amount]-1){
  34. 						$result[$key]++;
  35. 						$amount -= $key;
  36. 					}else{
  37. 						echo $amount."\n";
  38. 						print_r($result);
  39. 						exit("Неверный путь");
  40. 					}
  41. 				}
  42. 				$i--;
  43. 				if($i<0){
  44. 					exit("Все пошло по пизде");
  45. 				}
  46. 			}
  47. 		}
  48.  
  49. 		$resultStr = "";
  50. 		foreach ($result as $key => $value) {
  51. 			if($value != 0){
  52. 				$resultStr = $resultStr."{$value}x{$key} ";
  53. 			}
  54. 		}
  55.  
  56. 		echo $resultStr."\n";
  57. 	}
  58.  
  59.  
  60. 	$amount = 34;
  61.  
  62. 	$banknotes = array (
  63. 		2 => 3,
  64. 		5 => 10,
  65. 		10 => 1
  66. 	);
  67.  
  68. 	echo "Сумма: {$amount}\n";
  69. 	$rez = calculateDelivery($banknotes, $amount);
  70. ?>
Success #stdin #stdout 0.03s 52480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Сумма: 34
2x2 4x5 1x10
https://ideone.com/9sAV08
language:
PHP (php 7.3.5)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!