fork(1) download 
  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. //Удаляем из массива купюры которых нет в наличии
  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.     $billsTmp = $bills;
  29.     foreach ($billsTmp as $bill => $count) {
  30.         if ($count == 0) {
  31.             continue;
  32.         }
  33.         if (($sum >= $bill) && ($canIssue[$sum - $bill][0] + 1 < $canIssue[$sum][0])) {
  34.             if ($canIssue[$sum - $bill][1][$bill] != 0) {
  35.                 $canIssue[$sum][0] = $canIssue[$sum - $bill][0] + 1;
  36.                 $billsTmp[$bill] = $canIssue[$sum - $bill][1][$bill];
  37.                 --$billsTmp[$bill];
  38.             }
  39.         }
  40.     }
  41.     $canIssue[$sum][1] = $billsTmp;
  42. }
  43.  
  44. if ($canIssue[$input][0] == INF) {
  45.     echo "Выдача невозможна";
  46. } else {
  47.     while ($input > 0) {
  48.         foreach ($bills as $bill => $count) {
  49.             if (isset($canIssue[$input -$bill][0])) {
  50.                 if ($canIssue[$input - $bill][0] == $canIssue[$input][0] - 1) {
  51.                     $tmp .= $bill . ' ';
  52.                     $input -= $bill;
  53.                     break;
  54.                 }
  55.             }
  56.         }
  57.     }
  58. }
  59. print_r($tmp);
Success #stdin #stdout 0.04s 20568KB
comments (?)
stdin 
Standard input is empty
stdout 
2000 2000 2000 200 200 200
https://ideone.com/Kf8L5g
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!