Самая дешёвая выборка

Условие для любых kk монет равносильно условию для самой дешёвой выборки. В неё берём как можно больше монет меньшего достоинства. Их количество на столе равно NN, если первое указанное достоинство меньше, и C−NC-N в обратном случае; в выборку входит минимум этого количества и kk. Остальные монеты выборки имеют большее достоинство. На двух соответствующих участках минимальная сумма линейна.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Применение в задаче

Шаг 1. Условие для любых kk монет равносильно условию для самой дешёвой выборки. В неё берём как можно больше монет меньшего достоинства. Их количество на столе равно NN, если первое указанное достоинство меньше, и C−NC-N в обратном случае; в выборку входит минимум этого количества и kk. Остальные монеты выборки имеют большее достоинство. На двух соответствующих участках минимальная сумма линейна.
Sвсе=2N+5(800−N)S_{\text{все}}=2 N+5 \left(800-N\right)
k=300k=300

Всё решение и условие задачи Решить задачу

Следующий шаг

Задачи по этому методу