fork(6) download
copy 
  1. <?php
  2. header("Content-Type: text/plain");
  3. mb_internal_encoding('utf-8');
  4.  
  5. /*  Задача про банкомат
  6.  *  пытаемся выдать 6600 р.
  7.  *  число банкнот: 1 по 5000, 4 по 2000, 1 по 500, 3 по 200
  8.  */
  9.  
  10. // Требуемая сумма 
  11. $amount = 6600;
  12.  
  13. // Ответ: сумма размены, номиналы и их количество 
  14. $ans = array ('amount' => $amount); 
  15.  
  16. // Номиналы банкнот, количество
  17. $bills = Array (
  18.                 1 => Array ('value' => 200, 'quantity' => 3),
  19.                 2 => Array ('value' => 500, 'quantity' => 1),
  20.                 3 => Array ('value' => 2000, 'quantity' => 4),
  21.                 4 => Array ('value' => 5000, 'quantity' => 1)
  22. );
  23.  
  24. // Массив в котором мы храним результат вычислений $results[$numBill][$currentAmount]
  25. $results = array(); 
  26.  
  27. // Частичное заполнение массива
  28. // Для всех сумм банкнотой 0 размен не ввозможен (INF)
  29. for ($currentAmount = 0; $currentAmount <= $amount; $currentAmount++) {    
  30.     $results[0][$currentAmount] = INF;}
  31.  
  32. // Если просят разменять сумму 0, гордо протягиваем пустую ладонь (0 банкнот).
  33. for ($numBill = 0; $numBill <= count($bills); $numBill++) {    
  34.     $results[$numBill][0] = 0;
  35. }
  36.  
  37. // $currentAmount - текущая сумма, которую нужно выдать, увеличиваем от 1 до требуемой $amount
  38. for($currentAmount = 1; $currentAmount <= $amount; $currentAmount++) {
  39.  
  40.     // Перебираем все номиналы банкнот
  41.     foreach ($bills as $numBill => $bill) {
  42.  
  43.         // По умолчанию, текущую сумму можно выдать банкнотой предыдущего номинала.                       
  44.         $results[$numBill][$currentAmount] =  $results[$numBill-1][$currentAmount];
  45.  
  46.         // Есть ли банкноты текущего номинала и текущую сумму можно разменять текущим номиналом           
  47.         if ($bill['quantity']>0 && $currentAmount >= $bill['value']) {
  48.  
  49.             /*  Перебираем количество банкнот текущего номинала
  50.                 от минимально требуемого (или того что есть) до 1 */
  51.             for ($minQuant=min($bill['quantity'], intval(floor($currentAmount/$bill['value']))); $minQuant >= 1; $minQuant--) {
  52.  
  53.                 /*  Выбираем минимальное количество банкнот для размена между данной банкнотой и предыдущей
  54.                     если сумму меняем текущей банкнотой, то записываем количество банкнот
  55.                     для данного номинала и количество монет предыдущих номиналов, для размена остатка суммы  */
  56.                 $results[$numBill][$currentAmount] =  min($results[$numBill][$currentAmount], $results[$numBill-1][$currentAmount - $minQuant * $bill['value']] + $minQuant); 
  57.             }
  58.         }
  59.     }
  60. }   
  61.  
  62.  
  63. // Ф-я считает банкноты для размены требуемой суммы для Анона 
  64. // аргументы: массив с результатом, банкноты (номинал/кол-во), кол-во номиналов, сумма для выдачи, ответ
  65. function findAns($results, $bills, $numBill, $amount, $ans) {
  66.  
  67.     while ($results[$numBill][$amount] != 0) { 
  68.  
  69.         /*  если для размена текущей суммы количество банкнот прошлого номинала нужно столько же,
  70.             то переходим к предыдущему номиналу */
  71.         if ($results[$numBill-1][$amount] == $results[$numBill][$amount]) { 
  72.             $numBill--;
  73.  
  74.         /*  если текущую сумму можно несколько раз выдать текущей банкнотой, делаем это,
  75.             и добавляем текущую банкноту к результату и уменьшаем сумму выдачи на текущий номинал*/
  76.         } elseif ($results[$numBill][$amount] >= $results[$numBill][$amount-$bills[$numBill]['value']]) {
  77.             if (isset($ans[$bills[$numBill]['value']])) {
  78.                 $ans[$bills[$numBill]['value']]++;
  79.             } else {
  80.                  $ans[$bills[$numBill]['value']]=1;
  81.             }
  82.             $amount -= $bills[$numBill]['value'];
  83.  
  84.         /*  если остаток текущей суммы, после размена текущей банкнотой, можно выдать только
  85.             банкнотой предыдущего номинала, так тому и быть, + 1 к результату, переходим к
  86.             предыдущему номиналу и уменьшаем сумму выдачи на текущий номинал */   
  87.         } else {  
  88.             if (isset($ans[$bills[$numBill]['value']])) {
  89.                 $ans[$bills[$numBill]['value']]++;
  90.             } else {
  91.                  $ans[$bills[$numBill]['value']]=1;
  92.             }
  93.             $numBill--;
  94.             $amount -= $bills[$numBill]['value'];    
  95.         }
  96.     }
  97.     printAns ($ans); // отправляем ответ на печать
  98. }
  99. // Проверяем существует ли ответ для данной суммы, зовем findAns или ругаемся.
  100. function checkAns($results, $bills, $numBill, $amount, $ans) {
  101.     if ($results[$numBill][$amount]==INF) {
  102.         $ans['result']=NULL;
  103.         printAns ($ans); // отправляем ответ на печать
  104.     } else {
  105.         $ans = findAns($results, $bills, $numBill, $amount, $ans);
  106.     }
  107. }
  108.  
  109. // Выводим результат
  110. function printAns ($ans) {
  111.  
  112.     echo "Сумма: {$ans['amount']}\n";
  113.  
  114.     if ($ans['result']=NULL) {
  115.         echo "Требуемую сумму выдать невозможно";
  116.     } else {
  117.         echo "Выдача возможна, число купюр:\n";
  118.  
  119.         foreach($ans as $billValue => $quantity) {
  120.             if ($billValue!=0) {
  121.                 echo "{$quantity}x{$billValue}" . " ";
  122.             }
  123.         }
  124.     }
  125. }
  126.  
  127. // Запускаем проверку
  128. checkAns($results, $bills, count($bills), $amount, $ans);
  129. ?>
Success #stdin #stdout 0.1s 52480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Сумма: 6600
Выдача возможна, число купюр:
3x2000 3x200
https://ideone.com/gyBVtD
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!