<?php
$n = 120; // сумма
$s = array(10, 60, 100); // множество монет
$r = []; // сортировочные варианты
for ($x = 0; $x < count($s); $x++) { for ($y = 0; $y < count($s); $y++) { $sum = $s[$y];
if ($sum + $s[$x] > $n) {
continue;
}
$r[$x][$y][] = $sum;
while (true) {
if ($sum + $s[$x] > $n) {
break;
}
$sum += $s[$x];
$r[$x][$y][] = $s[$x];
}
}
}
$a = []; // возможные варианты
for ($x = 0; $x < count($r); $x++) { for ($y = 0; $y < count($r[$x]); $y++) { $a[] = $r[$x][$y];
}
}
}
$o = []; // оптимальные варианты
for ($x = 0; $x < count($a); $x++) { if (count($a[$x]) < $min) { }
}
for ($x = 0; $x < count($a); $x++) { if (count($a[$x]) == $min) { $o[] = $a[$x];
}
}
?>
PD9waHAKCiRuID0gMTIwOyAvLyDRgdGD0LzQvNCwCgokcyA9IGFycmF5KDEwLCA2MCwgMTAwKTsgLy8g0LzQvdC+0LbQtdGB0YLQstC+INC80L7QvdC10YIKCiRyID0gW107IC8vINGB0L7RgNGC0LjRgNC+0LLQvtGH0L3Ri9C1INCy0LDRgNC40LDQvdGC0YsKCmZvciAoJHggPSAwOyAkeCA8IGNvdW50KCRzKTsgJHgrKykgewogICAgZm9yICgkeSA9IDA7ICR5IDwgY291bnQoJHMpOyAkeSsrKSB7CiAgICAgICAgJHN1bSA9ICRzWyR5XTsKICAgICAgICBpZiAoJHN1bSArICRzWyR4XSA+ICRuKSB7CiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0KICAgICAgICAkclskeF1bJHldW10gPSAkc3VtOwogICAgICAgIHdoaWxlICh0cnVlKSB7CiAgICAgICAgICAgIGlmICgkc3VtICsgJHNbJHhdID4gJG4pIHsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICAgICAgICRzdW0gKz0gJHNbJHhdOwogICAgICAgICAgICAkclskeF1bJHldW10gPSAkc1skeF07CiAgICAgICAgfQogICAgfQp9CgokYSA9IFtdOyAvLyDQstC+0LfQvNC+0LbQvdGL0LUg0LLQsNGA0LjQsNC90YLRiwoKZm9yICgkeCA9IDA7ICR4IDwgY291bnQoJHIpOyAkeCsrKSB7CiAgICBmb3IgKCR5ID0gMDsgJHkgPCBjb3VudCgkclskeF0pOyAkeSsrKSB7CiAgICAgICAgaWYgKGFycmF5X3N1bSgkclskeF1bJHldKSA9PSAkbikgewogICAgICAgICAgICAkYVtdID0gJHJbJHhdWyR5XTsKICAgICAgICB9CiAgICB9Cn0KCiRvID0gW107IC8vINC+0L/RgtC40LzQsNC70YzQvdGL0LUg0LLQsNGA0LjQsNC90YLRiwokbWluID0gY291bnQoJGFbMF0pOwoKZm9yICgkeCA9IDA7ICR4IDwgY291bnQoJGEpOyAkeCsrKSB7CiAgICBpZiAoY291bnQoJGFbJHhdKSA8ICRtaW4pIHsKICAgICAgICAkbWluID0gY291bnQoJGFbJHhdKTsKICAgIH0KfQoKZm9yICgkeCA9IDA7ICR4IDwgY291bnQoJGEpOyAkeCsrKSB7CiAgICBpZiAoY291bnQoJGFbJHhdKSA9PSAkbWluKSB7CiAgICAgICAgJG9bXSA9ICRhWyR4XTsKICAgIH0KfQoKdmFyX2R1bXAoJG8pOwoKPz4=