Самая дешёвая выборка
Условие для любых монет равносильно условию для самой дешёвой выборки. В неё берём как можно больше монет меньшего достоинства. Их количество на столе равно , если первое указанное достоинство меньше, и в обратном случае; в выборку входит минимум этого количества и . Остальные монеты выборки имеют большее достоинство. На двух соответствующих участках минимальная сумма линейна.
Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.
Применение в задаче
Всё решение и условие задачи Решить задачу