Предположим, вы разрабатываете веб-приложение для загрузки файлов — этакий менеджер загрузок из прошлого. Но из-за ограничений на стороне сервера можете получать данные только пачками по несколько мегабайт в зависимости от местоположения сервера (притом в одной пачке могут лежать части разных файлов). А уже на фронте вы склеиваете их в нормальные файлы. Это всё усложняется тем, что все файлы заранее разбиты на части разных размеров. То есть какие-то файлы могут быть с частями по 7 МБ, какие-то — по 4 МБ, какие-то — по 5 МБ... Задача состоит в том, чтобы добавить в каждую пачку с сервера столько частей разных файлов, чтобы в итоге использовать максимальное количество доступного места.

Эта задача по своей сути — переформулировка задачи о рюкзаке, классической и очень известной задачи оптимизации.

Если мы будем решать её жадно, то получим примерно такой же алгоритм, какой мы использовали при подсчёте сдачи. Сначала будем складывать в нашу пачку, допустим, из 10 МБ самые большие части по 7 МБ. На этом наша пачка закончится, так как мы не сможем добавить в неё ни одну из доступных частей по 4 МБ или 5 МБ. Хотя если бы мы клали частями по 5 МБ, то заняли бы всё доступное пространство! Здесь жадный алгоритм дал сбой и выдал совсем неоптимальное, хотя и довольно хорошее решение.

Во многих подобных случаях иметь самое оптимальное решение необязательно — достаточно получить хотя бы «неплохой» результат. И в таких задачах жадные алгоритмы хороши — они просты для понимания и реализации, а их результаты приемлемы. Если же мы обязательно хотим получить идеальный ответ — можно попробовать решить задачу ещё одним способом, о котором мы поговорим в следующем разделе.