<?php
header("Content-Type: text/plain; charset=utf-8");
$amount = 5600;
$notes_available = [
100 => 0,
200 => 3,
500 => 1,
2000 => 4,
5000 => 1,
];
krsort($notes_available, SORT_NUMERIC
);
function check_withdraw($amount, $notes, $current_notes = []){
static $withdraw = [];
foreach($notes as $nominal => $quantity){
/* вычисляем максимальное количество банкнот текущего номинала для выдачи остатка */
$needed = (int)($amount / $nominal);
if ($quantity >= $needed):
$current_quantity = $needed;
else:
$current_quantity = $quantity;
endif;
/* вычисляем сумму для выдачи текущей банкнотой */
$current_summ = $current_quantity * $nominal;
/* убираем использованную валюту из массива, чтобы передать остальные в следующие итерации */
/* создаю отдельный массив с валютами для следующей итерации,
потому что текущий будет использоваться дальше в foreach */
$next_current_notes = $current_notes;
/* если купюр > 0, добавляем их количество и номинал в текущий набор в итерации */
if($current_quantity)
$next_current_notes[$nominal] = $current_quantity;
/* если остаток равен 0 - добавляем в массив выдачи */
if(!($amount - $current_summ)){
$withdraw[] = $next_current_notes;
}
check_withdraw($amount - $current_summ, $notes, $next_current_notes);
}
/* на выходе получаются все возможные комбинации купюр, при обработке я беру первую */
return $withdraw;
}
function get_message($withdraw, $amount){
echo "Сумма $amount:\n";
if(!empty($withdraw[0])){
echo "Выдача возможна, число купюр:\n";
foreach($withdraw[0] as $nominal => $quantity){
echo $nominal."x".$quantity." ";
}
}else{
echo "Выдача невозможна.";
}
}
$withdraw = check_withdraw($amount, $notes_available);
get_message($withdraw, $amount);
PD9waHAKaGVhZGVyKCJDb250ZW50LVR5cGU6IHRleHQvcGxhaW47IGNoYXJzZXQ9dXRmLTgiKTsKCiRhbW91bnQgPSA1NjAwOwoKJG5vdGVzX2F2YWlsYWJsZSA9IFsKICAgIDEwMCAgPT4gMCwKICAgIDIwMCAgPT4gMywKICAgIDUwMCAgPT4gMSwKICAgIDIwMDAgPT4gNCwKICAgIDUwMDAgPT4gMSwKXTsKCmtyc29ydCgkbm90ZXNfYXZhaWxhYmxlLCBTT1JUX05VTUVSSUMpOwoKZnVuY3Rpb24gY2hlY2tfd2l0aGRyYXcoJGFtb3VudCwgJG5vdGVzLCAkY3VycmVudF9ub3RlcyA9IFtdKXsKICAgIHN0YXRpYyAkd2l0aGRyYXcgPSBbXTsKCiAgICBmb3JlYWNoKCRub3RlcyBhcyAkbm9taW5hbCA9PiAkcXVhbnRpdHkpewogICAgICAgIC8qINCy0YvRh9C40YHQu9GP0LXQvCDQvNCw0LrRgdC40LzQsNC70YzQvdC+0LUg0LrQvtC70LjRh9C10YHRgtCy0L4g0LHQsNC90LrQvdC+0YIg0YLQtdC60YPRidC10LPQviDQvdC+0LzQuNC90LDQu9CwINC00LvRjyDQstGL0LTQsNGH0Lgg0L7RgdGC0LDRgtC60LAgKi8KICAgICAgICAkbmVlZGVkID0gKGludCkoJGFtb3VudCAvICRub21pbmFsKTsKCiAgICAgICAgaWYgKCRxdWFudGl0eSA+PSAkbmVlZGVkKToKICAgICAgICAgICAgJGN1cnJlbnRfcXVhbnRpdHkgPSAkbmVlZGVkOwogICAgICAgIGVsc2U6CiAgICAgICAgICAgICRjdXJyZW50X3F1YW50aXR5ID0gJHF1YW50aXR5OwogICAgICAgIGVuZGlmOwoKICAgICAgICAvKiDQstGL0YfQuNGB0LvRj9C10Lwg0YHRg9C80LzRgyDQtNC70Y8g0LLRi9C00LDRh9C4INGC0LXQutGD0YnQtdC5INCx0LDQvdC60L3QvtGC0L7QuSAqLwogICAgICAgICRjdXJyZW50X3N1bW0gPSAkY3VycmVudF9xdWFudGl0eSAqICRub21pbmFsOwoKICAgICAgICAvKiDRg9Cx0LjRgNCw0LXQvCDQuNGB0L/QvtC70YzQt9C+0LLQsNC90L3Rg9GOINCy0LDQu9GO0YLRgyDQuNC3INC80LDRgdGB0LjQstCwLCDRh9GC0L7QsdGLINC/0LXRgNC10LTQsNGC0Ywg0L7RgdGC0LDQu9GM0L3Ri9C1INCyINGB0LvQtdC00YPRjtGJ0LjQtSDQuNGC0LXRgNCw0YbQuNC4ICovCiAgICAgICAgdW5zZXQoJG5vdGVzWyRub21pbmFsXSk7CgogICAgICAgIC8qINGB0L7Qt9C00LDRjiDQvtGC0LTQtdC70YzQvdGL0Lkg0LzQsNGB0YHQuNCyINGBINCy0LDQu9GO0YLQsNC80Lgg0LTQu9GPINGB0LvQtdC00YPRjtGJ0LXQuSDQuNGC0LXRgNCw0YbQuNC4LAogICAgICAgICAgINC/0L7RgtC+0LzRgyDRh9GC0L4g0YLQtdC60YPRidC40Lkg0LHRg9C00LXRgiDQuNGB0L/QvtC70YzQt9C+0LLQsNGC0YzRgdGPINC00LDQu9GM0YjQtSDQsiBmb3JlYWNoICovCiAgICAgICAgJG5leHRfY3VycmVudF9ub3RlcyA9ICRjdXJyZW50X25vdGVzOwogICAgICAgIAogICAgICAgIC8qINC10YHQu9C4INC60YPQv9GO0YAgPiAwLCDQtNC+0LHQsNCy0LvRj9C10Lwg0LjRhSDQutC+0LvQuNGH0LXRgdGC0LLQviDQuCDQvdC+0LzQuNC90LDQuyDQsiDRgtC10LrRg9GJ0LjQuSDQvdCw0LHQvtGAINCyINC40YLQtdGA0LDRhtC40LggKi8KICAgICAgICBpZigkY3VycmVudF9xdWFudGl0eSkKICAgICAgICAgICAgJG5leHRfY3VycmVudF9ub3Rlc1skbm9taW5hbF0gPSAkY3VycmVudF9xdWFudGl0eTsKCiAgICAgICAgLyog0LXRgdC70Lgg0L7RgdGC0LDRgtC+0Log0YDQsNCy0LXQvSAwIC0g0LTQvtCx0LDQstC70Y/QtdC8INCyINC80LDRgdGB0LjQsiDQstGL0LTQsNGH0LggKi8KICAgICAgICBpZighKCRhbW91bnQgLSAkY3VycmVudF9zdW1tKSl7CiAgICAgICAgICAgICR3aXRoZHJhd1tdID0gJG5leHRfY3VycmVudF9ub3RlczsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgY2hlY2tfd2l0aGRyYXcoJGFtb3VudCAtICRjdXJyZW50X3N1bW0sICRub3RlcywgJG5leHRfY3VycmVudF9ub3Rlcyk7CiAgICB9CgogICAgLyog0L3QsCDQstGL0YXQvtC00LUg0L/QvtC70YPRh9Cw0Y7RgtGB0Y8g0LLRgdC1INCy0L7Qt9C80L7QttC90YvQtSDQutC+0LzQsdC40L3QsNGG0LjQuCDQutGD0L/RjtGALCDQv9GA0Lgg0L7QsdGA0LDQsdC+0YLQutC1INGPINCx0LXRgNGDINC/0LXRgNCy0YPRjiAqLwogICAgcmV0dXJuICR3aXRoZHJhdzsKfQoKZnVuY3Rpb24gZ2V0X21lc3NhZ2UoJHdpdGhkcmF3LCAkYW1vdW50KXsKICAgIGVjaG8gItCh0YPQvNC80LAgJGFtb3VudDpcbiI7CiAgICBpZighZW1wdHkoJHdpdGhkcmF3WzBdKSl7CgogICAgICAgIGVjaG8gItCS0YvQtNCw0YfQsCDQstC+0LfQvNC+0LbQvdCwLCDRh9C40YHQu9C+INC60YPQv9GO0YA6XG4iOwogICAgICAgIGZvcmVhY2goJHdpdGhkcmF3WzBdIGFzICRub21pbmFsID0+ICRxdWFudGl0eSl7CiAgICAgICAgICAgIGVjaG8gJG5vbWluYWwuIngiLiRxdWFudGl0eS4iICI7CiAgICAgICAgfQogICAgfWVsc2V7CiAgICAgICAgZWNobyAi0JLRi9C00LDRh9CwINC90LXQstC+0LfQvNC+0LbQvdCwLiI7CiAgICB9Cn0KCiR3aXRoZHJhdyA9IGNoZWNrX3dpdGhkcmF3KCRhbW91bnQsICRub3Rlc19hdmFpbGFibGUpOwoKZ2V0X21lc3NhZ2UoJHdpdGhkcmF3LCAkYW1vdW50KTs=