fork(1) download 
  1. <?php
  2.  
  3. error_reporting(-1);
  4.  
  5. //требуемая сумма
  6. $amount = 6600;
  7.  
  8. //запас наличных 
  9. $nominals = array(100, 200, 500, 1000, 2000, 5000);
  10. $check = array();
  11. $check[0] = array(
  12.    100      =>   0,
  13.    200      =>   3,
  14.    500      =>   1,
  15.    1000     =>   0,
  16.    2000     =>   4,
  17.    5000     =>   1
  18. );
  19.  
  20. /*  Алгоритм начинает свою работу с того что массив $solutionsStorage заполняется значением 9999
  21. значение 9999 в данном случае аналог false. Ключ в данном массиве - число, для которого ищется лучшее (меньшее) количество банкнот, которым можно выдать это число.
  22. Значение массива $solutionsStorage под ключём n - лучшее(меньшее) количество банкнот, которым можно выдать  число n.
  23. Значению $solutionsStorage с ключём 0 присваиваится целочисленное значение 0, так как сумму 0р можно выдать количеством 0 банкнот.
  24.  
  25. Далее цикл перебирает массив $solutionsStorage, и для каждого ключа(и каждого значения $amount до 6600 соответственно) находит лучшее(меньшее количество банкнот) алгоритмом описанным ниже.
  26. Если же определённую сумму выдать нельзя, то у ключа равного этой сумме значение будет 9999 - то есть false.
  27. Чтобы лучше понять как действует алгоритм рассмотрим его работу поэтапно на примере суммы 100 р и 500р. 
  28.  
  29. $k = 100 (рассматривается ситуация, когда в банкомате есть купюра в 100р, в рабочем примере этой купюры в банкомате нет)
  30. строка 75: банкнота номиналом 100(все остальные банкноты не проходят первую проверку в строке 76)
  31. строка 76: $solutionsStorage[100 - 100] < $solutionsStorage[100](тут будет число 9999 в первом проходе цикла)
  32. вторая проверка в строке 76 нужна для двух целей. Первая цель - определить что данную сумму вообще возможно выдать
  33. имеющимися номиналами (если нельзя, то $solutionsStorage[$k - $nominals[$i]] будет больше или равно $solutionsStorage[$k]
  34. Вторая цель - определить минимальное количество банкнот, которым можно выдать сумму(более подробно будет рассмотренно
  35. в примере с суммой в 500р))
  36. строка 76: третья проверка определяет есть ли нужная купюра номиналом $i в банкомате
  37. строка 77: если все три проверки успешны, значению $solutionsStorage[100] присваивается значение $solutionsStorage[0]
  38. строка 78: также значению $check[100] присваивается массив с количеством доступных банкнот, который находится в $check[0]
  39. строка 79: также в переменную $bestNominal записывается номинал банкноты - 100, также переменная $tic становится true
  40. далее, если все три проверки пройдены, и найден лучший номинал для суммы $k мы отнимаем 1 банкноту номинала $bestNominal
  41. из массива с количеством доступных банкнот(строка 85), добавляем одну банкноту к истинному решению в массив $solutionsStorage с ключем 100 (строка 86)
  42. таким образом значение $solutionsStorage[100] становится 1, и в заключении задаем переменной $tic значение false\
  43.  
  44. $k = 500 (рассматривается ситуация, когда в банкомате есть купюра в 100р, в рабочем примере этой купюры в банкомате нет)
  45. Первая итерация вложенного цикла{
  46. В этот раз я не буду акцентировать внимание на первой проверке, сразу перейдём ко второй
  47. строка 75: банкнота номиналом 100р
  48. строка 76: $solutionsStorage[500 - 100](под этим ключем будет значение 2 банкноты, высчитанное ранее, 2 меньше чем 9999)
  49. строка 76: купюра с номиналом $nominals[$i] , то есть 100 в массиве с количеством доступных банкнот у нас тоже есть, значит третью проверку мы проходим
  50. далее присваиваем $solutionsStorage[500] значение 2 (купюры), прибавляем к этому значению 1, и вычитаем одну купюру этого номинала из
  51. банкомата, массив который представляет это теперь находится в $check[500]
  52. }
  53. Вторая итерация вложенного цикла{
  54. строка 75: банкнота номиналом 200р
  55. строка 76: $solutionsStorage[500 - 200](под этим ключем будет значение 2 банкноты, высчитанное ранее, 2  меньше чем 3, вторая проверка пройдена)
  56. Дальше идут примерно те же действия что и в первой итерации, с небольшими различиями (так, например значение $check[500] заполняется значением $check[300]
  57. вместо $check[400], и уже оттуда вычитается одна банкнота номиналом 200р)
  58. }
  59. Третья итерация вложенного цикла{
  60. строка 75: банкнота номиналом 500р
  61. строка 76: $solutionsStorage[500 - 500](под этим ключем будет значение 0 банкноты, высчитанное ранее, 0  меньше чем 3, вторая проверка пройдена)
  62. После выполняются те же действия что и в итерациях выше с небольшими различиями.
  63. }
  64. В итоге в $solutionsStorage[500] значение 1 (одна банкнота), а из $check[500] будет вычтена 1 банкнота номиналом 500р
  65. */
  66.  
  67. $tic = false; //переменная, которая позволяет или запрещает добавить одну банкноту к истинному решению, в зависимости от истинности выражения в строке 
  68. $bestNominal = 0;
  69. $solutionsStorage  = array();
  70. $solutionsStorage = array_fill(0, $amount + 1, 9999); // заполнение массива значением 9999, до $amount
  71. $solutionsStorage[0] = 0;
  72. for ($k = 1; $k < $amount + 1; $k++){
  73. 	for ($i = 0; $i < count($nominals); $i++){
  74. 		if ($k - $nominals[$i] >= 0 && $solutionsStorage[$k - $nominals[$i]] < $solutionsStorage[$k] && $check[$k - $nominals[$i]][$nominals[$i]] > 0){
  75. 			$solutionsStorage[$k] = $solutionsStorage[$k - $nominals[$i]];
  76. 			$check[$k] = $check[$k - $nominals[$i]]; //присвоение массиву в значении $k массива ($k - номинал банкноты)
  77. 			$bestNominal = $nominals[$i];
  78. 			$tic = true;
  79. 		}
  80.  
  81. 	}
  82. 	if($tic == true){       //прибавление банкноты к истинному решению, вычитание банкноты из банкомата
  83. 	$check[$k][$bestNominal] -= 1; 
  84.     $solutionsStorage[$k] += 1;
  85. 	$tic = false;
  86. 	}
  87. }
  88.  
  89. if ($solutionsStorage[$amount] >= 9999){
  90. 	echo 'выдать сумму невозможно';
  91. }
  92. else{
  93. 	if ($solutionsStorage[$amount] == 0){
  94. 	'выдано ноль банкнот';
  95.     }
  96.     else{
  97. 	echo "Сумма к выдаче:{$amount}\n";
  98. 	echo "выдано банкнот всего: {$solutionsStorage[$amount]}\n";
  99.     for($p = count($nominals) - 1; $p >= 0; $p--){
  100. 		$bankn = $check[0][$nominals[$p]] - $check[$amount][$nominals[$p]];
  101. 		echo "выдано {$bankn} банкнот номиналом {$nominals[$p]} рублей\n";
  102. 	    } 
  103.     }
  104. }
Success #stdin #stdout 0.02s 52488KB
comments (?)
stdin 
Standard input is empty
stdout 
Сумма к выдаче:6600
выдано банкнот всего: 6
выдано 0 банкнот номиналом 5000 рублей
выдано 3 банкнот номиналом 2000 рублей
выдано 0 банкнот номиналом 1000 рублей
выдано 0 банкнот номиналом 500 рублей
выдано 3 банкнот номиналом 200 рублей
выдано 0 банкнот номиналом 100 рублей
https://ideone.com/CT8F66
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!