fork(2) download
copy 
  1. <?php
  2. 	error_reporting(-1);
  3. 	mb_internal_encoding('utf-8');
  4.  
  5. 	function constructGraph($bills, $amount){
  6. 		global $topsOut, $topsIncluded, $weights;
  7. 		foreach($bills as $nomination => $quantity){
  8. 			do{
  9. 				if(($amount-$nomination)>=0 && ($bills[$nomination] - 1)>=0){
  10. 					array_push($topsOut, $amount);
  11. 					array_push($topsIncluded, $amount-$nomination);
  12. 					array_push($weights, $nomination);
  13. 					$amount = $amount - $nomination;
  14. 					$bills[$nomination]--;
  15. 					if($amount==0){
  16. 						return;
  17. 					}
  18. 				}
  19. 			}while($bills[$nomination]>0 && ($amount-$nomination)>=0);
  20. 		}
  21. 	}
  22.  
  23. 	// $amount = 54500;
  24. 	// $bills = array(
  25. 		// 5000 => 200,
  26. 		// 1000 => 0,
  27. 		// 500 => 5,
  28. 		// 100 => 23
  29. 	// );
  30.  
  31. 	$amount = 66600;
  32. 	$bills = array(
  33. 		50000 => 2,
  34. 		20000 => 3,
  35. 		5000 => 1,
  36. 		2000 => 4,
  37. 		500 => 1,
  38. 		200 => 3
  39. 	);
  40.  
  41. 	// $amount = 24;
  42. 	// $bills = array(
  43. 		// 10 => 1,
  44. 		// 5 => 5,
  45. 		// 1 => 5
  46. 	// );
  47.  
  48. 	// $amount = 8;
  49. 	// $bills = array(
  50. 		// 9 => 1,
  51. 		// 4 => 1,
  52. 		// 2 => 5
  53. 	// );
  54.  
  55.     $topsOut = array();
  56.     $topsIncluded = array();
  57.     $weights = array();
  58. 	$result = array_fill_keys(array_keys($bills), 0);
  59. 	$amountSave = $amount;
  60.  
  61. 	foreach($bills as $nomination => $quantity){
  62. 		if(($amount-$nomination)>=0 && ($bills[$nomination] - 1)>=0){
  63. 			array_push($topsOut, $amount);
  64. 			array_push($topsIncluded, $amount-$nomination);
  65. 			array_push($weights, $nomination);
  66. 			$bills[$nomination]--;
  67. 			constructGraph($bills, $amount-$nomination);
  68. 		}
  69. 	}
  70.  
  71. 	$num = array_search(0, $topsIncluded);
  72. 	$result[$weights[$num]]++;
  73. 	if($num){
  74. 		$n = $topsOut[$num];
  75. 		while($topsOut[$num]!=$amountSave){
  76. 			$num--;
  77. 			$result[$weights[$num]]++;
  78. 		}
  79. 	}
  80.  
  81. 	$resultStr = "";
  82. 	foreach ($result as $key => $value) {
  83. 		if($value != 0){
  84. 			$resultStr = $resultStr."{$value}x{$key} ";
  85. 		}
  86. 	}
  87. 	echo $resultStr."\n";
  88. ?>
Success #stdin #stdout 0.02s 52472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1x50000
https://ideone.com/7809o0
language:
PHP (php 7.3.5)
created:
9 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!