fork(1) 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 = 6600;
  32. 	$bills = array(
  33. 		5000 => 1,
  34. 		2000 => 4,
  35. 		500 => 1,
  36. 		200 => 3
  37. 	);
  38.  
  39. 	// $amount = 24;
  40. 	// $bills = array(
  41. 		// 10 => 1,
  42. 		// 5 => 5,
  43. 		// 1 => 5
  44. 	// );
  45.  
  46. 	// $amount = 8;
  47. 	// $bills = array(
  48. 		// 9 => 1,
  49. 		// 4 => 1,
  50. 		// 2 => 5
  51. 	// );
  52.  
  53.     $topsOut = array();
  54.     $topsIncluded = array();
  55.     $weights = array();
  56. 	$result = array_fill_keys(array_keys($bills), 0);
  57. 	$amountSave = $amount;
  58.  
  59. 	foreach($bills as $nomination => $quantity){
  60. 		if(($amount-$nomination)>=0 && ($bills[$nomination] - 1)>=0){
  61. 			array_push($topsOut, $amount);
  62. 			array_push($topsIncluded, $amount-$nomination);
  63. 			array_push($weights, $nomination);
  64. 			$bills[$nomination]--;
  65. 			constructGraph($bills, $amount-$nomination);
  66. 		}
  67. 	}
  68.  
  69. 	$num = array_search(0, $topsIncluded);
  70. 	$result[$weights[$num]]++;
  71. 	if($num){
  72. 		$n = $topsOut[$num];
  73. 		while($topsOut[$num]!=$amountSave){
  74. 			$num--;
  75. 			$result[$weights[$num]]++;
  76. 		}
  77. 	}
  78.  
  79. 	$resultStr = "";
  80. 	foreach ($result as $key => $value) {
  81. 		if($value != 0){
  82. 			$resultStr = $resultStr."{$value}x{$key} ";
  83. 		}
  84. 	}
  85. 	echo $resultStr."\n";
  86. ?>
Success #stdin #stdout 0.02s 52472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3x2000 3x200
https://ideone.com/lE757J
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!