<?php
/* Этот алгоритм начинает перебор с ближайшего к сумме значения, поэтому он найдет комбинацию быстрее. Каждую итерацию
высчитывается максимальное количество купюр следущего номинала, то есть мы не не перебираем купюры, заведомо превышающие сумму.*/
$money = 6600;
$bills = array( // Купюры по условию. Номинал купюры => количество купюр этого номинала 5000 => 1,
2000 => 4,
500 => 1,
200 => 3
);
$denominationOfBills = array( // Массив всех номиналов купюр 0 => 5000,
1 => 2000,
2 => 500,
3 => 200
);
$numberOfBills = array( // Количество купюр всех номиналов );
function generateCombinations($numberOfBills, $money, $denominationOfBills, $arrayValues = [], $N = 0)
{
# Высчитывается максимальное значение количества купюр перебираемого номинала, чтобы не превысить требуемую сумму
if ($N < 4) { /* Если не поставить это условие, то будет пробовать высчитываться следующее после последнего(несуществующее) лимитное значение */
$nextMaxLimit = floor(($money - sum
($arrayValues, $denominationOfBills)) / $denominationOfBills[$N]); if ($nextMaxLimit > max($numberOfBills[$N])) { $nextMaxLimit = max($numberOfBills[$N]); }
$numberOfBills[$N] = range($nextMaxLimit, 0); }
if (count($arrayValues) == count($denominationOfBills)) { // Когда кол-во элементов комбинации == кол-ву предоставленных номиналов yield $arrayValues; // Возвращаем комбинацию
} else {
foreach ($numberOfBills[$N] as $valueOnSquare) {
yield from generateCombinations
($numberOfBills, $money, $denominationOfBills, array_merge($arrayValues, [$valueOnSquare]), $N + 1); }
}
}
function sum($arrayValues, $denominationOfBills) // Функция высчитывающая сумму любой комбинации
{
$sum = 0;
$i = 0;
foreach ($arrayValues as $amount) {
$sum += $amount * $denominationOfBills[$i];
$i += 1;
}
return $sum;
}
$combinationGenerator = generateCombinations($numberOfBills, $money, $denominationOfBills);
foreach ($combinationGenerator as $arrayValues) {
if (sum($arrayValues, $denominationOfBills) == $money) {
echo "Комбинация с наименьшим кол-вом купюр надейна !" . PHP_EOL;
break;
}
}
# Вывод в требуемом формате
for ($i = 0; $i < count($arrayValues); $i++) { echo "{$denominationOfBills[$i]}x{$arrayValues[$i]} ";
}
/*function greedyAlgorithm($money, $bills) // Функция реализующая жадный алгоритм и подсчитывающая комбинацию купюр для выдачи нужной суммы.
Алгоритм выдаёт комбинацию, даже при том условии, если нельзя выдать сумму полностью
{
foreach ($bills as $denominationOfBills => $numberOfBills) {
$greedyNumber = floor($money / $denominationOfBills);
if ($greedyNumber > $numberOfBills) {
$greedyNumber = $numberOfBills;
}
$arrayValues[] = $greedyNumber;
$money -= $denominationOfBills * $greedyNumber;
}
return $arrayValues;
} */
PD9waHAKLyog0K3RgtC+0YIg0LDQu9Cz0L7RgNC40YLQvCDQvdCw0YfQuNC90LDQtdGCINC/0LXRgNC10LHQvtGAINGBINCx0LvQuNC20LDQudGI0LXQs9C+INC6INGB0YPQvNC80LUg0LfQvdCw0YfQtdC90LjRjywg0L/QvtGN0YLQvtC80YMg0L7QvSDQvdCw0LnQtNC10YIg0LrQvtC80LHQuNC90LDRhtC40Y4g0LHRi9GB0YLRgNC10LUuINCa0LDQttC00YPRjiDQuNGC0LXRgNCw0YbQuNGOCtCy0YvRgdGH0LjRgtGL0LLQsNC10YLRgdGPINC80LDQutGB0LjQvNCw0LvRjNC90L7QtSDQutC+0LvQuNGH0LXRgdGC0LLQviDQutGD0L/RjtGAINGB0LvQtdC00YPRidC10LPQviDQvdC+0LzQuNC90LDQu9CwLCDRgtC+INC10YHRgtGMINC80Ysg0L3QtSDQvdC1INC/0LXRgNC10LHQuNGA0LDQtdC8INC60YPQv9GO0YDRiywg0LfQsNCy0LXQtNC+0LzQviDQv9GA0LXQstGL0YjQsNGO0YnQuNC1INGB0YPQvNC80YMuKi8KZXJyb3JfcmVwb3J0aW5nKC0xKTsKCiRtb25leSA9IDY2MDA7CgokYmlsbHMgPSBhcnJheSggLy8g0JrRg9C/0Y7RgNGLINC/0L4g0YPRgdC70L7QstC40Y4uINCd0L7QvNC40L3QsNC7INC60YPQv9GO0YDRiyA9PiDQutC+0LvQuNGH0LXRgdGC0LLQviDQutGD0L/RjtGAINGN0YLQvtCz0L4g0L3QvtC80LjQvdCw0LvQsAogICAgNTAwMCA9PiAxLAogICAgMjAwMCA9PiA0LAogICAgNTAwID0+IDEsCiAgICAyMDAgPT4gMwopOwoKJGRlbm9taW5hdGlvbk9mQmlsbHMgPSBhcnJheSggLy8g0JzQsNGB0YHQuNCyINCy0YHQtdGFINC90L7QvNC40L3QsNC70L7QsiDQutGD0L/RjtGACiAgICAwID0+IDUwMDAsCiAgICAxID0+IDIwMDAsCiAgICAyID0+IDUwMCwKICAgIDMgPT4gMjAwCik7CgokbnVtYmVyT2ZCaWxscyA9IGFycmF5KCAvLyDQmtC+0LvQuNGH0LXRgdGC0LLQviDQutGD0L/RjtGAINCy0YHQtdGFINC90L7QvNC40L3QsNC70L7QsgogICAgMCA9PiByYW5nZSgwLCAxKSwKICAgIDEgPT4gcmFuZ2UoMCwgNCksCiAgICAyID0+IHJhbmdlKDAsIDEpLAogICAgMyA9PiByYW5nZSgwLCAzKQopOwoKZnVuY3Rpb24gZ2VuZXJhdGVDb21iaW5hdGlvbnMoJG51bWJlck9mQmlsbHMsICRtb25leSwgJGRlbm9taW5hdGlvbk9mQmlsbHMsICRhcnJheVZhbHVlcyA9IFtdLCAkTiA9IDApCnsKCiAgICAjINCS0YvRgdGH0LjRgtGL0LLQsNC10YLRgdGPINC80LDQutGB0LjQvNCw0LvRjNC90L7QtSDQt9C90LDRh9C10L3QuNC1INC60L7Qu9C40YfQtdGB0YLQstCwINC60YPQv9GO0YAg0L/QtdGA0LXQsdC40YDQsNC10LzQvtCz0L4g0L3QvtC80LjQvdCw0LvQsCwg0YfRgtC+0LHRiyDQvdC1INC/0YDQtdCy0YvRgdC40YLRjCDRgtGA0LXQsdGD0LXQvNGD0Y4g0YHRg9C80LzRgwogICAgaWYgKCROIDwgNCkgeyAvKiDQldGB0LvQuCDQvdC1INC/0L7RgdGC0LDQstC40YLRjCDRjdGC0L4g0YPRgdC70L7QstC40LUsINGC0L4g0LHRg9C00LXRgiDQv9GA0L7QsdC+0LLQsNGC0Ywg0LLRi9GB0YfQuNGC0YvQstCw0YLRjNGB0Y8g0YHQu9C10LTRg9GO0YnQtdC1INC/0L7RgdC70LUg0L/QvtGB0LvQtdC00L3QtdCz0L4o0L3QtdGB0YPRidC10YHRgtCy0YPRjtGJ0LXQtSkg0LvQuNC80LjRgtC90L7QtSDQt9C90LDRh9C10L3QuNC1ICovCiAgICAgICAgJG5leHRNYXhMaW1pdCA9IGZsb29yKCgkbW9uZXkgLSBzdW0oJGFycmF5VmFsdWVzLCAkZGVub21pbmF0aW9uT2ZCaWxscykpIC8gJGRlbm9taW5hdGlvbk9mQmlsbHNbJE5dKTsKICAgICAgICBpZiAoJG5leHRNYXhMaW1pdCA+IG1heCgkbnVtYmVyT2ZCaWxsc1skTl0pKSB7CiAgICAgICAgICAgICRuZXh0TWF4TGltaXQgPSBtYXgoJG51bWJlck9mQmlsbHNbJE5dKTsKICAgICAgICB9CiAgICAgICAgJG51bWJlck9mQmlsbHNbJE5dID0gcmFuZ2UoJG5leHRNYXhMaW1pdCwgMCk7CiAgICB9CgogICAgaWYgKGNvdW50KCRhcnJheVZhbHVlcykgPT0gY291bnQoJGRlbm9taW5hdGlvbk9mQmlsbHMpKSB7IC8vINCa0L7Qs9C00LAg0LrQvtC7LdCy0L4g0Y3Qu9C10LzQtdC90YLQvtCyINC60L7QvNCx0LjQvdCw0YbQuNC4ID09INC60L7Quy3QstGDINC/0YDQtdC00L7RgdGC0LDQstC70LXQvdC90YvRhSDQvdC+0LzQuNC90LDQu9C+0LIKICAgICAgICB5aWVsZCAkYXJyYXlWYWx1ZXM7IC8vINCS0L7Qt9Cy0YDQsNGJ0LDQtdC8INC60L7QvNCx0LjQvdCw0YbQuNGOCiAgICB9IGVsc2UgewogICAgICAgIGZvcmVhY2ggKCRudW1iZXJPZkJpbGxzWyROXSBhcyAkdmFsdWVPblNxdWFyZSkgewogICAgICAgICAgICB5aWVsZCBmcm9tIGdlbmVyYXRlQ29tYmluYXRpb25zKCRudW1iZXJPZkJpbGxzLCAkbW9uZXksICRkZW5vbWluYXRpb25PZkJpbGxzLCBhcnJheV9tZXJnZSgkYXJyYXlWYWx1ZXMsIFskdmFsdWVPblNxdWFyZV0pLCAkTiArIDEpOwogICAgICAgIH0KICAgIH0KfQoKZnVuY3Rpb24gc3VtKCRhcnJheVZhbHVlcywgJGRlbm9taW5hdGlvbk9mQmlsbHMpIC8vINCk0YPQvdC60YbQuNGPINCy0YvRgdGH0LjRgtGL0LLQsNGO0YnQsNGPINGB0YPQvNC80YMg0LvRjtCx0L7QuSDQutC+0LzQsdC40L3QsNGG0LjQuAp7CiAgICAkc3VtID0gMDsKICAgICRpID0gMDsKICAgIGZvcmVhY2ggKCRhcnJheVZhbHVlcyBhcyAkYW1vdW50KSB7CiAgICAgICAgJHN1bSArPSAkYW1vdW50ICogJGRlbm9taW5hdGlvbk9mQmlsbHNbJGldOwogICAgICAgICRpICs9IDE7CiAgICB9CiAgICByZXR1cm4gJHN1bTsKfQoKJGNvbWJpbmF0aW9uR2VuZXJhdG9yID0gZ2VuZXJhdGVDb21iaW5hdGlvbnMoJG51bWJlck9mQmlsbHMsICRtb25leSwgJGRlbm9taW5hdGlvbk9mQmlsbHMpOwpmb3JlYWNoICgkY29tYmluYXRpb25HZW5lcmF0b3IgYXMgJGFycmF5VmFsdWVzKSB7CiAgICBpZiAoc3VtKCRhcnJheVZhbHVlcywgJGRlbm9taW5hdGlvbk9mQmlsbHMpID09ICRtb25leSkgewogICAgICAgIGVjaG8gItCa0L7QvNCx0LjQvdCw0YbQuNGPINGBINC90LDQuNC80LXQvdGM0YjQuNC8INC60L7Quy3QstC+0Lwg0LrRg9C/0Y7RgCDQvdCw0LTQtdC50L3QsCAhIiAuIFBIUF9FT0w7CiAgICAgICAgcHJpbnRfcigkYXJyYXlWYWx1ZXMpOwogICAgICAgIGJyZWFrOwogICAgfQogICAgcHJpbnRfcigkYXJyYXlWYWx1ZXMpOwoKfQojINCS0YvQstC+0LQg0LIg0YLRgNC10LHRg9C10LzQvtC8INGE0L7RgNC80LDRgtC1CmZvciAoJGkgPSAwOyAkaSA8IGNvdW50KCRhcnJheVZhbHVlcyk7ICRpKyspIHsKICAgIGVjaG8gInskZGVub21pbmF0aW9uT2ZCaWxsc1skaV19eHskYXJyYXlWYWx1ZXNbJGldfSAiOwp9CgoKCgoKCgovKmZ1bmN0aW9uIGdyZWVkeUFsZ29yaXRobSgkbW9uZXksICRiaWxscykgLy8gINCk0YPQvdC60YbQuNGPINGA0LXQsNC70LjQt9GD0Y7RidCw0Y8g0LbQsNC00L3Ri9C5INCw0LvQs9C+0YDQuNGC0Lwg0Lgg0L/QvtC00YHRh9C40YLRi9Cy0LDRjtGJ0LDRjyDQutC+0LzQsdC40L3QsNGG0LjRjiDQutGD0L/RjtGAINC00LvRjyDQstGL0LTQsNGH0Lgg0L3Rg9C20L3QvtC5INGB0YPQvNC80YsuCiDQkNC70LPQvtGA0LjRgtC8INCy0YvQtNCw0ZHRgiDQutC+0LzQsdC40L3QsNGG0LjRjiwg0LTQsNC20LUg0L/RgNC4INGC0L7QvCDRg9GB0LvQvtCy0LjQuCwg0LXRgdC70Lgg0L3QtdC70YzQt9GPINCy0YvQtNCw0YLRjCDRgdGD0LzQvNGDINC/0L7Qu9C90L7RgdGC0YzRjgp7CiAgICBmb3JlYWNoICgkYmlsbHMgYXMgJGRlbm9taW5hdGlvbk9mQmlsbHMgPT4gJG51bWJlck9mQmlsbHMpIHsKICAgICAgICAkZ3JlZWR5TnVtYmVyID0gZmxvb3IoJG1vbmV5IC8gJGRlbm9taW5hdGlvbk9mQmlsbHMpOwogICAgICAgIGlmICgkZ3JlZWR5TnVtYmVyID4gJG51bWJlck9mQmlsbHMpIHsKICAgICAgICAgICAgJGdyZWVkeU51bWJlciA9ICRudW1iZXJPZkJpbGxzOwogICAgICAgIH0KICAgICAgICAkYXJyYXlWYWx1ZXNbXSA9ICRncmVlZHlOdW1iZXI7CiAgICAgICAgJG1vbmV5IC09ICRkZW5vbWluYXRpb25PZkJpbGxzICogJGdyZWVkeU51bWJlcjsKICAgIH0KICAgIHJldHVybiAkYXJyYXlWYWx1ZXM7Cn0gKi8=