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. $suitableCombinations = [];
  21.  
  22. function generateCombinations($n, $arrayValues, $banknotes, $N)
  23. {
  24.     global $money, $nominals, $suitableCombinations;
  25.     if (count($arrayValues) == $n) {
  26.         if (checkingCombination($arrayValues, $money, $nominals)) {
  27.             $suitableCombinations[] = checkingCombination($arrayValues, $money, $nominals);
  28.         }
  29.         return $arrayValues;
  30.     }
  31.  
  32.     foreach ($banknotes[$N] as $valueOnSquare) {
  33.         generateCombinations($n, array_merge($arrayValues, [$valueOnSquare]), $banknotes, $N + 1);
  34.     }
  35.  
  36. }
  37.  
  38. function checkingCombination($arrayValues, $money, $nominals)
  39. {
  40.     $i = 0;
  41.     $sum = 0;
  42.     foreach ($nominals as $nominal => $amount) {
  43.         $sum += $arrayValues[$i] * $nominal; //Кол-во банкнот: {$arrayValue[$i]}. Номинал банкноты {$nominal}".
  44.         $i += 1;
  45.     }
  46.     if ($sum == $money) {
  47.         return $arrayValues;
  48.     }
  49. }
  50.  
  51. generateCombinations(4, [], $banknotes, 0);
  52.  
  53. echo "Подходящие комбинации".PHP_EOL;
  54. print_r($suitableCombinations);
  55.  
  56. $bestCombination = [INF];
  57. foreach ($suitableCombinations as $combination) {
  58.     if (array_sum($combination) < array_sum($bestCombination)) {
  59.         $bestCombination = $combination;
  60.     }
  61. }
  62. echo "Лучшая комбинация с наименьшим количеством купюр".PHP_EOL;
  63. print_r($bestCombination);
  64.  
  65. $answer = array_combine(array_keys($nominals), $bestCombination);
  66.  
  67. foreach ($answer as $nominals => $theNumberOfBills) {
  68.     echo "{$theNumberOfBills}x{$nominals} ";
  69. }
  70.  
Success #stdin #stdout 0.02s 24504KB
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/5L3qJh
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!