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

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!