Математика сборов

Знаете эту ситуацию, когда собираете рюкзак в поездку и не можете решить что влезет а что нет? Типа "вот эту книжку взять или ту"? Может, ещё одну футболку? А зарядка точно нужна? Представляете как тяжело деду морозу собирать свой мешок подарков! В математике есть целый класс задач про это — так и называется «задача о рюкзаке». Первые попытки её описать были ещё в позапрошлом веке, ух!

Формально звучит так: есть набор предметов, у каждого своя ценность и свой вес, а рюкзак выдерживает только N килограммов. Задача - набрать самое ценное, но не порвать рюкзак. И ценного побольше, пожалуйста! И вот тут начинается самое интересное — это одна из тех задач, которые выглядят просто, но решаются ОЧЕНЬ сложно. Настолько, что она попадает в класс NP-полных задач — высшая лига сложности в информатике. Нормального решения нет, и даже на малых N полная засада.

🍌 Я каждый раз вспоминаю эту проблему когда покупаю бананы. В детстве мне как-то дали задание "купи X, Y, Z, а если останутся деньги — купи бананов". Я до сих помню, что в том магазе была овощная палатка по центру здания, и денег осталось условно на 1.7 кг, я это посчитал и попросил продавщицу взвесить. Она ОЧЕНЬ разозлилась, начала доказывать что "бананы никто не покупает по килограмму, только поштучно, ты что совсем больной". Но на мой вопрос "а почему тогда цена за килограмм?" ей было нечем крыть 😁

Той же математикой занимаются службы доставки, пытаясь уместить посылки в фургон, или даже сами части посылки внутрь посылки. Только там ещё и трёхмерная версия, тоже NP-полная. Так что в следующий раз когда будете злиться на курьера — помните, возможно прямо сейчас курьер решает одну из сложнейших математических задач! 🥡