fork download
copy 
  1. <?php
  2. /* Этот алгоритм начинает перебор с ближайшего к сумме значения, поэтому он найдет комбинацию быстрее. Каждую итерацию
  3. высчитывается максимальное количество купюр следущего номинала, то есть мы не не перебираем купюры, заведомо превышающие сумму.*/
  4. error_reporting(-1);
  5.  
  6. $money = 6600;
  7.  
  8. $bills = array( // Купюры по условию. Номинал купюры => количество купюр этого номинала
  9.     5000 => 1,
  10.     2000 => 4,
  11.     500 => 1,
  12.     200 => 3
  13. );
  14.  
  15. $denominationOfBills = array( // Массив всех номиналов купюр
  16.     0 => 5000,
  17.     1 => 2000,
  18.     2 => 500,
  19.     3 => 200
  20. );
  21.  
  22. $numberOfBills = array( // Количество купюр всех номиналов
  23.     0 => range(0, 1),
  24.     1 => range(0, 4),
  25.     2 => range(0, 1),
  26.     3 => range(0, 3)
  27. );
  28.  
  29. function generateCombinations($numberOfBills, $money, $denominationOfBills, $arrayValues = [], $N = 0)
  30. {
  31.  
  32.     # Высчитывается максимальное значение количества купюр перебираемого номинала, чтобы не превысить требуемую сумму
  33.     if ($N < 4) { /* Если не поставить это условие, то будет пробовать высчитываться следующее после последнего(несуществующее) лимитное значение */
  34.         $nextMaxLimit = floor(($money - sum($arrayValues, $denominationOfBills)) / $denominationOfBills[$N]);
  35.         if ($nextMaxLimit > max($numberOfBills[$N])) {
  36.             $nextMaxLimit = max($numberOfBills[$N]);
  37.         }
  38.         $numberOfBills[$N] = range($nextMaxLimit, 0);
  39.     }
  40.  
  41.     if (count($arrayValues) == count($denominationOfBills)) { // Когда кол-во элементов комбинации == кол-ву предоставленных номиналов
  42.         yield $arrayValues; // Возвращаем комбинацию
  43.     } else {
  44.         foreach ($numberOfBills[$N] as $valueOnSquare) {
  45.             yield from generateCombinations($numberOfBills, $money, $denominationOfBills, array_merge($arrayValues, [$valueOnSquare]), $N + 1);
  46.         }
  47.     }
  48. }
  49.  
  50. function sum($arrayValues, $denominationOfBills) // Функция высчитывающая сумму любой комбинации
  51. {
  52.     $sum = 0;
  53.     $i = 0;
  54.     foreach ($arrayValues as $amount) {
  55.         $sum += $amount * $denominationOfBills[$i];
  56.         $i += 1;
  57.     }
  58.     return $sum;
  59. }
  60.  
  61. $combinationGenerator = generateCombinations($numberOfBills, $money, $denominationOfBills);
  62. foreach ($combinationGenerator as $arrayValues) {
  63.     if (sum($arrayValues, $denominationOfBills) == $money) {
  64.         echo "Комбинация с наименьшим кол-вом купюр надейна !" . PHP_EOL;
  65.         print_r($arrayValues);
  66.         break;
  67.     }
  68.     print_r($arrayValues);
  69.  
  70. }
  71. # Вывод в требуемом формате
  72. for ($i = 0; $i < count($arrayValues); $i++) {
  73.     echo "{$denominationOfBills[$i]}x{$arrayValues[$i]} ";
  74. }
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82. /*function greedyAlgorithm($money, $bills) //  Функция реализующая жадный алгоритм и подсчитывающая комбинацию купюр для выдачи нужной суммы.
  83.  Алгоритм выдаёт комбинацию, даже при том условии, если нельзя выдать сумму полностью
  84. {
  85.     foreach ($bills as $denominationOfBills => $numberOfBills) {
  86.         $greedyNumber = floor($money / $denominationOfBills);
  87.         if ($greedyNumber > $numberOfBills) {
  88.             $greedyNumber = $numberOfBills;
  89.         }
  90.         $arrayValues[] = $greedyNumber;
  91.         $money -= $denominationOfBills * $greedyNumber;
  92.     }
  93.     return $arrayValues;
  94. } */
Success #stdin #stdout 0.02s 24312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Array
(
    [0] => 1
    [1] => 0
    [2] => 1
    [3] => 3
)
Array
(
    [0] => 1
    [1] => 0
    [2] => 1
    [3] => 2
)
Array
(
    [0] => 1
    [1] => 0
    [2] => 1
    [3] => 1
)
Array
(
    [0] => 1
    [1] => 0
    [2] => 1
    [3] => 0
)
Array
(
    [0] => 1
    [1] => 0
    [2] => 0
    [3] => 3
)
Array
(
    [0] => 1
    [1] => 0
    [2] => 0
    [3] => 2
)
Array
(
    [0] => 1
    [1] => 0
    [2] => 0
    [3] => 1
)
Array
(
    [0] => 1
    [1] => 0
    [2] => 0
    [3] => 0
)
Array
(
    [0] => 0
    [1] => 3
    [2] => 1
    [3] => 0
)
Комбинация с наименьшим кол-вом купюр надейна !
Array
(
    [0] => 0
    [1] => 3
    [2] => 0
    [3] => 3
)
5000x0 2000x3 500x0 200x3
https://ideone.com/KB7yZi
language:
PHP (php 7.3.5)
created:
3 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!