fork download 
  1. <?php
  2. header("Content-Type: text/plain; charset=utf-8");
  3.  
  4. $amount = 6600;
  5.  
  6. $notes_available = [
  7.     100  => 0,
  8.     200  => 3,
  9.     500  => 1,
  10.     2000 => 4,
  11.     5000 => 4,
  12. ];
  13.  
  14. krsort($notes_available, SORT_NUMERIC);
  15.  
  16. $stack = array_combine(array_keys($notes_available), array_fill(0, count($notes_available), 0));
  17.  
  18. function check_withdraw($notes, $nominal, $amount, $stack)
  19. {
  20.     foreach($notes as $nominal => $note){
  21.  
  22.         $temp_notes = $notes;
  23.         $temp_stack = $stack;
  24.  
  25.         $key = array_search($nominal, array_keys($temp_notes));
  26.  
  27.         @$next_nominal = array_keys($temp_notes)[$key + 1];
  28.  
  29.         $total_amount = 0;
  30.  
  31.         foreach($stack as $total_nominal => $quantity){
  32.             $total_amount += $total_nominal*$quantity;
  33.         }
  34.  
  35.         //если купюра есть и влезает - повторяем цикл с ней же
  36.         if(($total_amount + $nominal < $amount) and $temp_notes[$nominal]) {
  37.  
  38.             $temp_stack[$nominal]++;
  39.             $temp_notes[$nominal]--;
  40.             $temp_stack = check_withdraw($temp_notes, $nominal, $amount, $temp_stack);
  41.  
  42.         //если сумма соответствует - заканчивам цикл
  43.         }elseif(($total_amount + $nominal) == $amount and $temp_notes[$nominal]){
  44.  
  45.             $temp_stack[$nominal]++;
  46.             $temp_notes[$nominal]--;
  47.  
  48.         //иначе пробуем добавить купюру следующего номинала по убыванию
  49.         }elseif(isset($next_nominal) and array_sum(array_values($temp_notes))){
  50.  
  51.             unset($temp_notes[$nominal]);
  52.             $temp_stack = check_withdraw($temp_notes, $next_nominal, $amount, $temp_stack);
  53.  
  54.         }else{
  55.             continue;
  56.         }
  57.  
  58.         $check_stack_amount = 0;
  59.         foreach($temp_stack as $total_nominal => $quantity){
  60.             $check_stack_amount += $total_nominal*$quantity;
  61.         }
  62.         if($check_stack_amount==$amount){
  63.             return $temp_stack;
  64.         }
  65.  
  66.     }
  67.     return $temp_stack;
  68. }
  69.  
  70. function show_result($withdraw, $amount){
  71.     echo "Сумма $amount:\n\n";
  72.     if(array_sum($withdraw)){
  73.  
  74.         echo "Выдача возможна, число купюр:\n\n";
  75.         foreach($withdraw as $nominal => $quantity){
  76.             echo $nominal."x".$quantity."\n";
  77.         }
  78.     }else{
  79.         echo "Выдача невозможна.";
  80.     }
  81. }
  82.  
  83. show_result(check_withdraw($notes_available, false, $amount, $stack), $amount);
Success #stdin #stdout 0.04s 20520KB
comments (?)
stdin 
Standard input is empty
stdout 
Сумма 6600:

Выдача возможна, число купюр:

5000x0
2000x3
500x0
200x3
100x0
https://ideone.com/OtC2Nx
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!