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.  
  9. 		$amountSave = $amount;
  10. 		$INF = 1000000000;
  11. 		$minBanknotes = array();
  12. 		$minBanknotes[0][0] = 0;
  13.  
  14. 		for($m=0; $m<=$amount; $m++){
  15. 			$minBanknotes[0][$m] = $m==0?0:$INF;
  16. 			$p=1;
  17. 			foreach ($banknotes as $key => $value) {
  18. 				if($m <= $key-1){
  19. 					$minBanknotes[$p][$m] = $minBanknotes[$p-1][$m];
  20. 				}else{
  21. 					$minBanknotes[$p][$m] = min($minBanknotes[$p-1][$m], $minBanknotes[$p][$m-$key] + 1);
  22. 				}
  23. 				$p++;	
  24. 			}
  25. 		}
  26.  
  27. 		for($i=count($banknotes);$i>=1;$i--){
  28. 			$result = array_fill_keys(array_keys($banknotes), 0);
  29. 			$amount = $amountSave;
  30.  
  31. 			if ($minBanknotes[$i][$amount]==$INF){
  32. 				exit("Данным набором банкнот сумму выдать невозможно");
  33. 			}else{
  34. 				while($amount>0){
  35. 					foreach ($minBanknotes[$i] as $key => $value) {
  36. 						if ($minBanknotes[$i][$amount-$key] == $minBanknotes[$i][$amount]-1){
  37. 							$result[$key]++;
  38. 							$amount -= $key;
  39. 							break;
  40. 						}
  41. 					}
  42. 				}
  43. 			}
  44.  
  45. 			$resultStr = "";
  46. 			foreach ($result as $key => $value) {
  47. 				if($value != 0){
  48. 					$resultStr = $resultStr."{$value}x{$key} ";
  49. 				}
  50. 			}
  51. 			echo $resultStr."\n";			
  52. 		}
  53. 	}
  54.  
  55. 	$amount = 66;
  56.  
  57. 	$banknotes = array (
  58. 		2 => 3,
  59. 		5 => 1,
  60. 		20 => 4,
  61. 		50 => 1
  62. 	);
  63.  
  64. 	echo "Сумма: {$amount}\n";
  65. 	calculateDelivery($banknotes, $amount);
  66. ?>
Success #stdin #stdout 0.02s 52432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Сумма: 66
3x2 2x5 1x50 
3x2 3x20 
3x2 12x5 
33x2
https://ideone.com/WFlK6J
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!