Проблема заключается в следующем:
У вас есть n длин пути в км, которые нужно разделить на m дней так, чтобы максимальная сумма длин в день была минимальна. Например. Продолжительность поездки [1,5,2,6,8,3,2], разделенная на 3 дня, дает [1,5,2] [6] [8,3,2], поскольку максимальная сумма продолжительности дня равна самое низкое, чего мы можем достичь.
Существует ли некий алгоритм, описывающий решение такой проблемы? Я столкнулся с проблемой упаковки мусорного ведра и рюкзаком, но ни одна из них не затрагивает мою проблему. Я могу представить, что это может быть небольшая модификация упаковки мусорного ведра, но не делайте выводов.
O(n * m)
- person uSeemSurprised   schedule 23.08.2016[1,5,2,6,8,3,2], [], []
, где минимальная продолжительность дня равна 0, что лучше, чем 6. В любом случае, в наивном решении вы можете просто использовать binpacking и используйте бинарный поиск по параметру громкости. - person Bakuriu   schedule 23.08.2016m
было сведено к минимуму. - person uSeemSurprised   schedule 23.08.2016