fork download
copy 
  1. <?php
  2.  
  3. error_reporting(-1);
  4.  
  5. $money = 6600;
  6.  
  7. $nominals = array(
  8.     5000 => 1,
  9.     2000 => 4,
  10.     500 => 1,
  11.     200 => 3
  12. );
  13. $banknotes = array(
  14.     0 => range(0, 1),
  15.     1 => range(0, 4),
  16.     2 => range(0, 1),
  17.     3 => range(0, 3)
  18. );
  19.  
  20. function generateCombinations($n, $arrayValues, $banknotes, $N)
  21. {
  22.     if (count($arrayValues) == $n) {
  23.         yield $arrayValues;
  24.         return $arrayValues;
  25.     }
  26.  
  27.     foreach ($banknotes[$N] as $valueOnSquare) {
  28.         yield from generateCombinations($n, array_merge($arrayValues, [$valueOnSquare]), $banknotes, $N + 1);
  29.     }
  30.  
  31. }
  32.  
  33. function checkingCombination($arrayValues, $money, $nominals)
  34. {
  35.     $i = 0;
  36.     $sum = 0;
  37.     foreach ($nominals as $nominal => $amount) {
  38.         $sum += $arrayValues[$i] * $nominal; //Кол-во банкнот: {$arrayValue[$i]}. Номинал банкноты {$nominal}".
  39.         $i += 1;
  40.     }
  41.     if ($sum == $money) {
  42.         return $arrayValues;
  43.     }
  44. }
  45.  
  46.  
  47. $generator = generateCombinations(4, [], $banknotes, 0);
  48. foreach ($generator as $arrayValues) {
  49.     if (checkingCombination($arrayValues, $money, $nominals)) {
  50.         $suitableCombinations[] = checkingCombination($arrayValues, $money, $nominals);
  51.     }
  52. }
  53.  
  54. echo "Подходящие комбинации";
  55. print_r($suitableCombinations);
  56.  
  57. $bestCombination = [INF];
  58. foreach ($suitableCombinations as $combination) {
  59.     if (array_sum($combination) < array_sum($bestCombination)) {
  60.         $bestCombination = $combination;
  61.     }
  62. }
  63. echo "Лучшая комбинация с наименьшим количеством купюр";
  64. print_r($bestCombination);
  65.  
  66. $answer = array_combine(array_keys($nominals), $bestCombination);
  67.  
  68. foreach ($answer as $nominals => $theNumberOfBills) {
  69.     echo "{$theNumberOfBills}x{$nominals} ";
  70. }
Success #stdin #stdout 0.02s 24244KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Подходящие комбинацииArray
(
    [0] => Array
        (
            [0] => 0
            [1] => 3
            [2] => 0
            [3] => 3
        )

)
Лучшая комбинация с наименьшим количеством купюрArray
(
    [0] => 0
    [1] => 3
    [2] => 0
    [3] => 3
)
0x5000 3x2000 0x500 3x200
https://ideone.com/6tgkDv
language:
PHP (php 7.3.5)
created:
4 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!