fork download
  1. <?php
  2. header("Content-Type: text/plain; charset=utf-8");
  3.  
  4. $amount = 11000;
  5.  
  6. $notes_available = [
  7. 100 => 1,
  8. 200 => 1,
  9. 500 => 1,
  10. 2000 => 4,
  11. 5000 => 4,
  12. ];
  13.  
  14. krsort($notes_available, SORT_NUMERIC);
  15.  
  16. function check_withdraw($amount, $notes, $current_notes = []){
  17. static $withdraw = [];
  18.  
  19. foreach($notes as $nominal => $quantity){
  20. /* вычисляем максимальное количество банкнот текущего номинала для выдачи остатка */
  21. $needed = (int)($amount / $nominal);
  22.  
  23. if ($quantity >= $needed):
  24. $current_quantity = $needed;
  25. else:
  26. $current_quantity = $quantity;
  27. endif;
  28.  
  29. /* вычисляем сумму для выдачи текущей банкнотой */
  30. $current_summ = $current_quantity * $nominal;
  31.  
  32. /* убираем использованную валюту из массива, чтобы передать остальные в следующие итерации */
  33. unset($notes[$nominal]);
  34.  
  35. /* создаю отдельный массив с валютами для следующей итерации,
  36.   потому что текущий будет использоваться дальше в foreach */
  37. $next_current_notes = $current_notes;
  38.  
  39. /* если купюр > 0, добавляем их количество и номинал в текущий набор в итерации */
  40. if($current_quantity)
  41. $next_current_notes[$nominal] = $current_quantity;
  42.  
  43. /* если остаток равен 0 - добавляем в массив выдачи */
  44. if(!($amount - $current_summ)){
  45. $withdraw[] = $next_current_notes;
  46. }
  47.  
  48. check_withdraw($amount - $current_summ, $notes, $next_current_notes);
  49. }
  50.  
  51. /* на выходе получаются все возможные комбинации купюр, при обработке я беру первую */
  52. return $withdraw;
  53. }
  54.  
  55. function get_message($withdraw, $amount){
  56. echo "Сумма $amount:\n";
  57. if(!empty($withdraw[0])){
  58.  
  59. echo "Выдача возможна, число купюр:\n";
  60. foreach($withdraw[0] as $nominal => $quantity){
  61. echo $nominal."x".$quantity." ";
  62. }
  63. }else{
  64. echo "Выдача невозможна.";
  65. }
  66. }
  67.  
  68. $withdraw = check_withdraw($amount, $notes_available);
  69.  
  70. get_message($withdraw, $amount);
Success #stdin #stdout 0.01s 20568KB
stdin
Standard input is empty
stdout
Сумма 11000:
Выдача невозможна.