Level up!

Сложность любой задачи, для которой существует алгоритмическое решение, оценивается с учетом времени, которое необходимо для ее решения или проверки решения. Например, класс задач NP — это задачи, решение которых можно проверить за полиномиальное время, то есть за время, которое зависит от объема входных данных как многочлен (есть замечательная задача, за доказательство которой обещают миллион долларов, связанная с P и NP, но о ней в следующий раз). Соответственно, задача называется NP-полной, если любую задачу из класса NP можно свести к ней. NP-полных задач много.

N + 1 совместно с компанией Level Group предлагают читателям попробовать на практике, насколько сложны такие задачи. В качестве модели мы предлагаем задачу о рюкзаке в нашей собственной геометрической трактовке: пользователю нужно сложить неправильные фигуры пентамино (это фигурки, составленные из пяти кубиков) так, чтобы затягивающий их контур — тот самый условный рюкзак из названия — имел минимальную возможную площадь. Похожего рода задачи приходится решать строителям для оптимизации стройки ежедневно: роль фигур здесь играют процессы, поставки, сроки зависящих друг от друга работ, параметры нагрузок и стоимость материалов, а объем рюкзака — эффективность реализации конечного проекта. Разумеется, главный интерес тут в том, чтобы эта эффективность была максимальной. То есть, когда все фигурки в модели сложены наилучшим образом.

В общем, хватит болтать, играйте!