<?php
$bills = Array(10, 50, 100, 200, 500, 1000, 2000); // какие виды банкнот есть $countOfBills = count($bills); // кол-во видов банкнот $needleMoney = 6600; // сумма которую надо выдать
// 1 часть алгоритма
$INF = PHP_INT_MAX; //Бесконечность
$F = Array(); //Массив вида: Требуемая сумма => Минимальное количество купюр для её выдачи $F[0] = 0; //Ноль гривен выдать нельзя
for ($i = 1; $i <= $needleMoney; ++$i) { //Флажок i идет от единицы до суммы, которую необходимо выдать
$F[$i] = $INF; //По умолчанию считаем что вывод невозможен
for ($j = 0; $j < $countOfBills; ++$j) { //Массив проходит по всем банкнотам, его флажок j служит ключем для массива с банкнотами
if ($i >= $bills[$j] && $F[$i - $bills[$j]] + 1 < $F[$i]) { /*Если $i больше чем текущая банкнота и
F[$i-ТекущаяБанкнота] +1 меньше чем количество банкнот для $i */
$F[$i] = $F[$i - $bills[$j]] + 1; //Тогда определяется новое количество банкнот для $i, оно равно F[$i-ТекущаяБанкнота] +1
}
}
}
// 2 часть алгоритма
if ($F[$needleMoney] == $INF) { //Если количество купюр для выдачи необходимой суммы бесконечно
echo "Требуемую сумму выдать невозможно\r\n"; // Выводим сообщение об этом
} else { //В другом случае
while ($needleMoney > 0) { //Пока необходимая сумма больше нуля
for ($i = 0; $i < $countOfBills; ++$i) { //Цикл фор, в котором перебираются номиналы
if ($F[$needleMoney - $bills[$i]] == $F[$needleMoney] - 1) { //Если F[Необходимая сумма МИНУС купюра данного номинала == F[Необходимая сума]-1 ]
echo $bills[$i] . " "; //Выводим эту купюру
$needleMoney -= $bills[$i]; //Минусуем от необходимой суммы купюру
break; //Конец
}
}
}
}
PD9waHAKCmVycm9yX3JlcG9ydGluZygtMSk7CgokYmlsbHMgPSBBcnJheSgxMCwgNTAsIDEwMCwgMjAwLCA1MDAsIDEwMDAsIDIwMDApOyAvLyDQutCw0LrQuNC1INCy0LjQtNGLINCx0LDQvdC60L3QvtGCINC10YHRgtGMCiRjb3VudE9mQmlsbHMgPSBjb3VudCgkYmlsbHMpOyAvLyDQutC+0Lst0LLQviDQstC40LTQvtCyINCx0LDQvdC60L3QvtGCCiRuZWVkbGVNb25leSA9IDY2MDA7IC8vINGB0YPQvNC80LAg0LrQvtGC0L7RgNGD0Y4g0L3QsNC00L4g0LLRi9C00LDRgtGMCgovLyAxINGH0LDRgdGC0Ywg0LDQu9Cz0L7RgNC40YLQvNCwCiRJTkYgPSBQSFBfSU5UX01BWDsgLy/QkdC10YHQutC+0L3QtdGH0L3QvtGB0YLRjAokRiA9IEFycmF5KCk7IC8v0JzQsNGB0YHQuNCyINCy0LjQtNCwOiDQotGA0LXQsdGD0LXQvNCw0Y8g0YHRg9C80LzQsCA9PiDQnNC40L3QuNC80LDQu9GM0L3QvtC1INC60L7Qu9C40YfQtdGB0YLQstC+INC60YPQv9GO0YAg0LTQu9GPINC10ZEg0LLRi9C00LDRh9C4CiRGWzBdID0gMDsgLy/QndC+0LvRjCDQs9GA0LjQstC10L0g0LLRi9C00LDRgtGMINC90LXQu9GM0LfRjwoKZm9yICgkaSA9IDE7ICRpIDw9ICRuZWVkbGVNb25leTsgKyskaSkgeyAvL9Ck0LvQsNC20L7QuiBpINC40LTQtdGCINC+0YIg0LXQtNC40L3QuNGG0Ysg0LTQviDRgdGD0LzQvNGLLCDQutC+0YLQvtGA0YPRjiDQvdC10L7QsdGF0L7QtNC40LzQviDQstGL0LTQsNGC0YwKCiAgICAkRlskaV0gPSAkSU5GOyAvL9Cf0L4g0YPQvNC+0LvRh9Cw0L3QuNGOINGB0YfQuNGC0LDQtdC8INGH0YLQviDQstGL0LLQvtC0INC90LXQstC+0LfQvNC+0LbQtdC9CiAgICBmb3IgKCRqID0gMDsgJGogPCAkY291bnRPZkJpbGxzOyArKyRqKSB7IC8v0JzQsNGB0YHQuNCyINC/0YDQvtGF0L7QtNC40YIg0L/QviDQstGB0LXQvCDQsdCw0L3QutC90L7RgtCw0LwsINC10LPQviDRhNC70LDQttC+0LogaiDRgdC70YPQttC40YIg0LrQu9GO0YfQtdC8INC00LvRjyDQvNCw0YHRgdC40LLQsCDRgSDQsdCw0L3QutC90L7RgtCw0LzQuAogICAgICAgIGlmICgkaSA+PSAkYmlsbHNbJGpdICYmICRGWyRpIC0gJGJpbGxzWyRqXV0gKyAxIDwgJEZbJGldKSB7IC8q0JXRgdC70LggJGkg0LHQvtC70YzRiNC1INGH0LXQvCDRgtC10LrRg9GJ0LDRjyDQsdCw0L3QutC90L7RgtCwINC4CiAgICAgICAgICAgIEZbJGkt0KLQtdC60YPRidCw0Y/QkdCw0L3QutC90L7RgtCwXSArMSDQvNC10L3RjNGI0LUg0YfQtdC8INC60L7Qu9C40YfQtdGB0YLQstC+INCx0LDQvdC60L3QvtGCINC00LvRjyAkaSAqLwogICAgICAgICAgICAkRlskaV0gPSAkRlskaSAtICRiaWxsc1skal1dICsgMTsgLy/QotC+0LPQtNCwINC+0L/RgNC10LTQtdC70Y/QtdGC0YHRjyDQvdC+0LLQvtC1INC60L7Qu9C40YfQtdGB0YLQstC+INCx0LDQvdC60L3QvtGCINC00LvRjyAkaSwg0L7QvdC+INGA0LDQstC90L4gRlskaS3QotC10LrRg9GJ0LDRj9CR0LDQvdC60L3QvtGC0LBdICsxCiAgICAgICAgfQogICAgfQp9CgovLyAyINGH0LDRgdGC0Ywg0LDQu9Cz0L7RgNC40YLQvNCwCmlmICgkRlskbmVlZGxlTW9uZXldID09ICRJTkYpIHsgLy/QldGB0LvQuCDQutC+0LvQuNGH0LXRgdGC0LLQviDQutGD0L/RjtGAINC00LvRjyDQstGL0LTQsNGH0Lgg0L3QtdC+0LHRhdC+0LTQuNC80L7QuSDRgdGD0LzQvNGLINCx0LXRgdC60L7QvdC10YfQvdC+CiAgICBlY2hvICLQotGA0LXQsdGD0LXQvNGD0Y4g0YHRg9C80LzRgyDQstGL0LTQsNGC0Ywg0L3QtdCy0L7Qt9C80L7QttC90L5cclxuIjsgLy8g0JLRi9Cy0L7QtNC40Lwg0YHQvtC+0LHRidC10L3QuNC1INC+0LEg0Y3RgtC+0LwKfSBlbHNlIHsgLy/QkiDQtNGA0YPQs9C+0Lwg0YHQu9GD0YfQsNC1CiAgICB3aGlsZSAoJG5lZWRsZU1vbmV5ID4gMCkgeyAvL9Cf0L7QutCwINC90LXQvtCx0YXQvtC00LjQvNCw0Y8g0YHRg9C80LzQsCDQsdC+0LvRjNGI0LUg0L3Rg9C70Y8KICAgICAgICBmb3IgKCRpID0gMDsgJGkgPCAkY291bnRPZkJpbGxzOyArKyRpKSB7IC8v0KbQuNC60Lsg0YTQvtGALCDQsiDQutC+0YLQvtGA0L7QvCDQv9C10YDQtdCx0LjRgNCw0Y7RgtGB0Y8g0L3QvtC80LjQvdCw0LvRiwogICAgICAgICAgICBpZiAoJEZbJG5lZWRsZU1vbmV5IC0gJGJpbGxzWyRpXV0gPT0gJEZbJG5lZWRsZU1vbmV5XSAtIDEpIHsgLy/QldGB0LvQuCBGW9Cd0LXQvtCx0YXQvtC00LjQvNCw0Y8g0YHRg9C80LzQsCDQnNCY0J3Qo9ChINC60YPQv9GO0YDQsCDQtNCw0L3QvdC+0LPQviDQvdC+0LzQuNC90LDQu9CwID09IEZb0J3QtdC+0LHRhdC+0LTQuNC80LDRjyDRgdGD0LzQsF0tMSBdCiAgICAgICAgICAgICAgICBlY2hvICRiaWxsc1skaV0gLiAiICI7IC8v0JLRi9Cy0L7QtNC40Lwg0Y3RgtGDINC60YPQv9GO0YDRgwogICAgICAgICAgICAgICAgJG5lZWRsZU1vbmV5IC09ICRiaWxsc1skaV07IC8v0JzQuNC90YPRgdGD0LXQvCDQvtGCINC90LXQvtCx0YXQvtC00LjQvNC+0Lkg0YHRg9C80LzRiyDQutGD0L/RjtGA0YMKICAgICAgICAgICAgICAgIGJyZWFrOyAvL9Ca0L7QvdC10YYKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQ==