fork download 
  1. <?php
  2. //Сколько выдать
  3. $input = 700;
  4. //Номиналы и количество имеющихся купюр
  5. $bills = array(
  6.     100 => 0,
  7.     200 => 1,
  8.     500 => 1,
  9.     1000 => 0,
  10.     2000 => 2,
  11.     5000 => 1
  12. );
  13. //Упорядочить валюты по убыванию
  14. krsort($bills);
  15. //Количество выданных купюр
  16. $issued = array_fill_keys(array_flip($bills), 0);
  17. //Удаляем из массива купюры которых нет в наличии
  18. $toDelete = array_keys($bills, 0);
  19. foreach ($toDelete as $bill) {
  20.     unset($bills[$bill]);
  21. }
  22.  
  23. $tmp = '';
  24. $canIssue[0][0] = 0;
  25. $canIssue[0][1] = $bills;
  26. for ($sum = 1; $sum <= $input; ++$sum) {
  27.     $canIssue[$sum][0] = INF;
  28.     foreach ($bills as $bill => $count) {
  29.         if (($sum >= $bill) && ($canIssue[$sum - $bill][0] + 1 < $canIssue[$sum][0])) {
  30.             if ($canIssue[$sum - $bill][1][$bill] != 0) {
  31.                 $canIssue[$sum][0] = $canIssue[$sum - $bill][0] + 1;
  32.                 $canIssue[$sum][1][$bill] = $canIssue[$sum - $bill][1][$bill] - 1;
  33.             } else {
  34.                 $canIssue[$sum][1][$bill] = $bills[$bill];
  35.             }
  36.         } else {
  37.             $canIssue[$sum][1][$bill] = $bills[$bill];
  38.         }
  39.     }
  40. }
  41.  
  42. if ($canIssue[$input][0] == INF) {
  43.     echo "Выдача невозможна";
  44. } else {
  45.     while ($input > 0) {
  46.         foreach ($bills as $bill => $count) {
  47.             if (isset($canIssue[$input - $bill][0])) {
  48.                 if ($canIssue[$input - $bill][0] == $canIssue[$input][0] - 1) {
  49.                     $tmp .= $bill . ' ';
  50.                     $input -= $bill;
  51.                     break;
  52.                 }
  53.             }
  54.         }
  55.     }
  56. }
  57. print_r($tmp);
Success #stdin #stdout 0.01s 20520KB
comments (?)
stdin 
Standard input is empty
stdout 
500 200
https://ideone.com/I65ee9
language:
PHP (php 7.3.5)
created:
11 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!