История изменений
Исправление orm-i-auga, (текущая версия) :
Если там ограничение, что «отрезки неравные», то, похоже, эта задача NP-полная, так как она является NP-задачей и плюс к ней сводится другая NP-полная задача о сумме подмножеств. Значит «быстрого» общего решения нет, используй любое подходящее частное.
UPD Ну или можно ничего не придумывать, а просто использовать приближенные алгоритмы для решения задачи о сумме подмножеств.
Исправление orm-i-auga, :
Если там ограничение, что «отрезки неравные», то, похоже, эта задача NP-полная, так как она является NP-задачей и плюс к ней сводится другая NP-полная задача о сумме подмножеств. Значит «быстрого» общего решения нет, используй любое подходящее частное.
Исходная версия orm-i-auga, :
Если там ограничение, что «отрезки неравные», то, похоже, эта задача NP-полная, так как к ней сводится другая NP-полная задача о сумме подмножеств. Значит «быстрого» общего решения нет, используй любое подходящее частное.