This was an open problem until 2007, when an efficient algorithm based on dynamic programming was published.
Задача была открытой вплоть до 2007 года, когда опубликован эффективный алгоритм, основанный на динамическом программировании.