fork download
copy 
  1. <?php
  2. header("Content-Type: text/plain; charset=utf-8");
  3.  
  4. $amount = 5600;
  5.  
  6. $notes_available = [
  7.     100  => 0,
  8.     200  => 3,
  9.     500  => 1,
  10.     2000 => 4,
  11.     5000 => 1,
  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);
  71.  
  72. $amount2 = 600;
  73. $withdraw = check_withdraw($amount2, $notes_available);
  74. get_message($withdraw, $amount2);
  75.  
Success #stdin #stdout 0.01s 20520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Сумма 5600:
Выдача возможна, число купюр:
5000x1 200x3 Сумма 600:
Выдача возможна, число купюр:
5000x1 200x3
https://ideone.com/CVAqiL
language:
PHP (php 7.3.5)
created:
10 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!