<?php
/* Этот алгоритм начинает перебор с ближайшего к сумме значения, поэтому он найдет комбинацию быстрее. Каждую итерацию
высчитывается максимальное количество купюр следущего номинала, то есть мы не не перебираем купюры, заведомо превышающие сумму.*/
declare(strict_types=1);
$money = 6600;
$bills = array( // Купюры по условию. Номинал купюры => количество купюр этого номинала 5000 => 1,
2000 => 4,
500 => 1,
200 => 3
);
$i=0;
foreach ($bills as $denomination => $amount) {
$denominationOfBills[$i] = $denomination;
$numberOfBills[$i] = range(0, $amount); $i+=1;
}
# Вышестоящим циклом создаются следующие массивы, которые до этого писались вручную.
/*$denominationOfBills = [ // Массив всех номиналов купюр
0 => 5000,
1 => 2000,
2 => 500,
3 => 200
];
$numberOfBills = [ // Количество купюр всех номиналов
0 => range(0, 1),
1 => range(0, 4),
2 => range(0, 1),
3 => range(0, 3)
]; */
function generateCombinations
( array $numberOfBills, int
$money, array $denominationOfBills, array $combination = [], $N = 0) {
# Высчитывается максимальное значение количества купюр перебираемого номинала, чтобы не превысить требуемую сумму
if ($N < 4) { /* Если не поставить это условие, то будет пробовать высчитываться следующее после последнего(несуществующее) лимитное значение */
$nextMaxLimit = floor(($money - sum
($combination, $denominationOfBills)) / $denominationOfBills[$N]); if ($nextMaxLimit > max($numberOfBills[$N])) { $nextMaxLimit = max($numberOfBills[$N]); }
$numberOfBills[$N] = range($nextMaxLimit, 0); }
if (count($combination) == count($denominationOfBills)) { // Когда кол-во элементов комбинации == кол-ву предоставленных номиналов yield $combination; // Возвращаем комбинацию
} else {
foreach ($numberOfBills[$N] as $valueOnSquare) {
yield from generateCombinations
($numberOfBills, $money, $denominationOfBills, array_merge($combination, [$valueOnSquare]), $N + 1); }
}
}
function sum
(array $combination, array $denominationOfBills) : float
// Функция высчитывающая сумму любой комбинации {
$sum = 0;
$i = 0;
foreach ($combination as $amount) {
$sum += $amount * $denominationOfBills[$i];
$i += 1;
}
return $sum;
}
$combinationGenerator = generateCombinations($numberOfBills, $money, $denominationOfBills);
foreach ($combinationGenerator as $combination) {
if (sum($combination, $denominationOfBills) == $money) {
echo "Комбинация с наименьшим кол-вом купюр надейна !" . PHP_EOL;
break;
}
//print_r($combination);
}
# Вывод в требуемом формате
for ($i = 0; $i < count($combination); $i++) { echo "{$denominationOfBills[$i]}x{$combination[$i]} ";
}
PD9waHAKLyog0K3RgtC+0YIg0LDQu9Cz0L7RgNC40YLQvCDQvdCw0YfQuNC90LDQtdGCINC/0LXRgNC10LHQvtGAINGBINCx0LvQuNC20LDQudGI0LXQs9C+INC6INGB0YPQvNC80LUg0LfQvdCw0YfQtdC90LjRjywg0L/QvtGN0YLQvtC80YMg0L7QvSDQvdCw0LnQtNC10YIg0LrQvtC80LHQuNC90LDRhtC40Y4g0LHRi9GB0YLRgNC10LUuINCa0LDQttC00YPRjiDQuNGC0LXRgNCw0YbQuNGOCtCy0YvRgdGH0LjRgtGL0LLQsNC10YLRgdGPINC80LDQutGB0LjQvNCw0LvRjNC90L7QtSDQutC+0LvQuNGH0LXRgdGC0LLQviDQutGD0L/RjtGAINGB0LvQtdC00YPRidC10LPQviDQvdC+0LzQuNC90LDQu9CwLCDRgtC+INC10YHRgtGMINC80Ysg0L3QtSDQvdC1INC/0LXRgNC10LHQuNGA0LDQtdC8INC60YPQv9GO0YDRiywg0LfQsNCy0LXQtNC+0LzQviDQv9GA0LXQstGL0YjQsNGO0YnQuNC1INGB0YPQvNC80YMuKi8KCmRlY2xhcmUoc3RyaWN0X3R5cGVzPTEpOwplcnJvcl9yZXBvcnRpbmcoLTEpOwoKJG1vbmV5ID0gNjYwMDsKCiRiaWxscyA9IGFycmF5KCAvLyDQmtGD0L/RjtGA0Ysg0L/QviDRg9GB0LvQvtCy0LjRji4g0J3QvtC80LjQvdCw0Lsg0LrRg9C/0Y7RgNGLID0+INC60L7Qu9C40YfQtdGB0YLQstC+INC60YPQv9GO0YAg0Y3RgtC+0LPQviDQvdC+0LzQuNC90LDQu9CwCiAgICA1MDAwID0+IDEsCiAgICAyMDAwID0+IDQsCiAgICA1MDAgPT4gMSwKICAgIDIwMCA9PiAzCik7CgokaT0wOwpmb3JlYWNoICgkYmlsbHMgYXMgJGRlbm9taW5hdGlvbiA9PiAkYW1vdW50KSB7CiAgICAkZGVub21pbmF0aW9uT2ZCaWxsc1skaV0gPSAkZGVub21pbmF0aW9uOwogICAgJG51bWJlck9mQmlsbHNbJGldID0gcmFuZ2UoMCwgJGFtb3VudCk7CiAgICAkaSs9MTsKfQoKIyDQktGL0YjQtdGB0YLQvtGP0YnQuNC8INGG0LjQutC70L7QvCDRgdC+0LfQtNCw0Y7RgtGB0Y8g0YHQu9C10LTRg9GO0YnQuNC1INC80LDRgdGB0LjQstGLLCDQutC+0YLQvtGA0YvQtSDQtNC+INGN0YLQvtCz0L4g0L/QuNGB0LDQu9C40YHRjCDQstGA0YPRh9C90YPRji4KLyokZGVub21pbmF0aW9uT2ZCaWxscyA9IFsgLy8g0JzQsNGB0YHQuNCyINCy0YHQtdGFINC90L7QvNC40L3QsNC70L7QsiDQutGD0L/RjtGACiAgICAwID0+IDUwMDAsCiAgICAxID0+IDIwMDAsCiAgICAyID0+IDUwMCwKICAgIDMgPT4gMjAwCl07CgokbnVtYmVyT2ZCaWxscyA9IFsgLy8g0JrQvtC70LjRh9C10YHRgtCy0L4g0LrRg9C/0Y7RgCDQstGB0LXRhSDQvdC+0LzQuNC90LDQu9C+0LIKICAgIDAgPT4gcmFuZ2UoMCwgMSksCiAgICAxID0+IHJhbmdlKDAsIDQpLAogICAgMiA9PiByYW5nZSgwLCAxKSwKICAgIDMgPT4gcmFuZ2UoMCwgMykKXTsgKi8KCmZ1bmN0aW9uIGdlbmVyYXRlQ29tYmluYXRpb25zKCBhcnJheSAkbnVtYmVyT2ZCaWxscywgaW50ICRtb25leSwgYXJyYXkgJGRlbm9taW5hdGlvbk9mQmlsbHMsIGFycmF5ICRjb21iaW5hdGlvbiA9IFtdLCAkTiA9IDApCnsKCiAgICAjINCS0YvRgdGH0LjRgtGL0LLQsNC10YLRgdGPINC80LDQutGB0LjQvNCw0LvRjNC90L7QtSDQt9C90LDRh9C10L3QuNC1INC60L7Qu9C40YfQtdGB0YLQstCwINC60YPQv9GO0YAg0L/QtdGA0LXQsdC40YDQsNC10LzQvtCz0L4g0L3QvtC80LjQvdCw0LvQsCwg0YfRgtC+0LHRiyDQvdC1INC/0YDQtdCy0YvRgdC40YLRjCDRgtGA0LXQsdGD0LXQvNGD0Y4g0YHRg9C80LzRgwogICAgaWYgKCROIDwgNCkgeyAvKiDQldGB0LvQuCDQvdC1INC/0L7RgdGC0LDQstC40YLRjCDRjdGC0L4g0YPRgdC70L7QstC40LUsINGC0L4g0LHRg9C00LXRgiDQv9GA0L7QsdC+0LLQsNGC0Ywg0LLRi9GB0YfQuNGC0YvQstCw0YLRjNGB0Y8g0YHQu9C10LTRg9GO0YnQtdC1INC/0L7RgdC70LUg0L/QvtGB0LvQtdC00L3QtdCz0L4o0L3QtdGB0YPRidC10YHRgtCy0YPRjtGJ0LXQtSkg0LvQuNC80LjRgtC90L7QtSDQt9C90LDRh9C10L3QuNC1ICovCiAgICAgICAgJG5leHRNYXhMaW1pdCA9IGZsb29yKCgkbW9uZXkgLSBzdW0oJGNvbWJpbmF0aW9uLCAkZGVub21pbmF0aW9uT2ZCaWxscykpIC8gJGRlbm9taW5hdGlvbk9mQmlsbHNbJE5dKTsKICAgICAgICBpZiAoJG5leHRNYXhMaW1pdCA+IG1heCgkbnVtYmVyT2ZCaWxsc1skTl0pKSB7CiAgICAgICAgICAgICRuZXh0TWF4TGltaXQgPSBtYXgoJG51bWJlck9mQmlsbHNbJE5dKTsKICAgICAgICB9CiAgICAgICAgJG51bWJlck9mQmlsbHNbJE5dID0gcmFuZ2UoJG5leHRNYXhMaW1pdCwgMCk7CiAgICB9CgogICAgaWYgKGNvdW50KCRjb21iaW5hdGlvbikgPT0gY291bnQoJGRlbm9taW5hdGlvbk9mQmlsbHMpKSB7IC8vINCa0L7Qs9C00LAg0LrQvtC7LdCy0L4g0Y3Qu9C10LzQtdC90YLQvtCyINC60L7QvNCx0LjQvdCw0YbQuNC4ID09INC60L7Quy3QstGDINC/0YDQtdC00L7RgdGC0LDQstC70LXQvdC90YvRhSDQvdC+0LzQuNC90LDQu9C+0LIKICAgICAgICB5aWVsZCAkY29tYmluYXRpb247IC8vINCS0L7Qt9Cy0YDQsNGJ0LDQtdC8INC60L7QvNCx0LjQvdCw0YbQuNGOCiAgICB9IGVsc2UgewogICAgICAgIGZvcmVhY2ggKCRudW1iZXJPZkJpbGxzWyROXSBhcyAkdmFsdWVPblNxdWFyZSkgewogICAgICAgICAgICB5aWVsZCBmcm9tIGdlbmVyYXRlQ29tYmluYXRpb25zKCRudW1iZXJPZkJpbGxzLCAkbW9uZXksICRkZW5vbWluYXRpb25PZkJpbGxzLCBhcnJheV9tZXJnZSgkY29tYmluYXRpb24sIFskdmFsdWVPblNxdWFyZV0pLCAkTiArIDEpOwogICAgICAgIH0KICAgIH0KfQoKZnVuY3Rpb24gc3VtKGFycmF5ICRjb21iaW5hdGlvbiwgYXJyYXkgJGRlbm9taW5hdGlvbk9mQmlsbHMpIDogZmxvYXQgLy8g0KTRg9C90LrRhtC40Y8g0LLRi9GB0YfQuNGC0YvQstCw0Y7RidCw0Y8g0YHRg9C80LzRgyDQu9GO0LHQvtC5INC60L7QvNCx0LjQvdCw0YbQuNC4CnsKICAgICRzdW0gPSAwOwogICAgJGkgPSAwOwogICAgZm9yZWFjaCAoJGNvbWJpbmF0aW9uIGFzICRhbW91bnQpIHsKICAgICAgICAkc3VtICs9ICRhbW91bnQgKiAkZGVub21pbmF0aW9uT2ZCaWxsc1skaV07CiAgICAgICAgJGkgKz0gMTsKICAgIH0KICAgIHJldHVybiAkc3VtOwp9CgokY29tYmluYXRpb25HZW5lcmF0b3IgPSBnZW5lcmF0ZUNvbWJpbmF0aW9ucygkbnVtYmVyT2ZCaWxscywgJG1vbmV5LCAkZGVub21pbmF0aW9uT2ZCaWxscyk7CmZvcmVhY2ggKCRjb21iaW5hdGlvbkdlbmVyYXRvciBhcyAkY29tYmluYXRpb24pIHsKICAgIGlmIChzdW0oJGNvbWJpbmF0aW9uLCAkZGVub21pbmF0aW9uT2ZCaWxscykgPT0gJG1vbmV5KSB7CiAgICAgICAgZWNobyAi0JrQvtC80LHQuNC90LDRhtC40Y8g0YEg0L3QsNC40LzQtdC90YzRiNC40Lwg0LrQvtC7LdCy0L7QvCDQutGD0L/RjtGAINC90LDQtNC10LnQvdCwICEiIC4gUEhQX0VPTDsKICAgICAgICBwcmludF9yKCRjb21iaW5hdGlvbik7CiAgICAgICAgYnJlYWs7CiAgICB9CiAgICAvL3ByaW50X3IoJGNvbWJpbmF0aW9uKTsKCn0KIyDQktGL0LLQvtC0INCyINGC0YDQtdCx0YPQtdC80L7QvCDRhNC+0YDQvNCw0YLQtQpmb3IgKCRpID0gMDsgJGkgPCBjb3VudCgkY29tYmluYXRpb24pOyAkaSsrKSB7CiAgICBlY2hvICJ7JGRlbm9taW5hdGlvbk9mQmlsbHNbJGldfXh7JGNvbWJpbmF0aW9uWyRpXX0gIjsKfQ==