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