Блог

У меня есть набор интервалов, каждый из которых имеет определенную стоимость. Например

 [(0, 4, 10), (2, 6, 5), (5, 7, 2), (8, 10, 2), (5, 10, 10)]
 

Я хотел бы знать, существует ли подмножество интервалов, которое охватывает целые числа 1…10 (скажем) точно, не перекрывая друг друга и с общей стоимостью ниже заданного значения c . Стоимость покрытия — это произведение затрат на интервалы в покрытии.

В этом случае мы можем точно покрыть интервал с [(0, 4, 10), (5, 10, 10)] что и стоило 10*10=100 . Или мы можем покрыть интервал [(0,4,10), (5, 7, 2), (8, 10, 2)] что и стоило 10*2*2 = 40 .

Поэтому, если бы мы установили стоимость c=50 , то ответ был бы «ДА», а если бы мы установили c=30 , то ответ был бы «НЕТ».

Существует ли эффективный способ решения этой проблемы?

Мне было интересно, может ли это сделать какой-то вариант планирования взвешенных интервалов, но я не вижу, как внести необходимые изменения. Основная проблема заключается в том, что здесь мы заботимся только о покрытиях, которые покрывают весь интервал без перекрытий, и мы хотим минимизировать затраты на них.

Редактировать: Примечание @btillys комментарий об использовании журнала(стоимости) для веса ребер, это важно, так как нам нужен продукт затрат, а не сумма.

Да, существует эффективный способ решить эту проблему с помощью теории графов.

Пусть каждый интервал (a,b, cost) является узлом v , и пусть e это ребро между двумя узлами v1 = (a,b, cost) и v2 = (a2,b2, cost2) iff ‘a2 = b 1’ (неофициально: вы можете использовать v2, исходящий из v1).

Имейте начальный узел s , у которого есть ребро для всех узлов, a=0 и конечный узел f , у которого есть ребро для всех узлов b=10 .

Теперь проблема сводится к нахождению кратчайшего пути между s и f . Используя Djikstra или что-то подобное, сложность должна быть O(E VlogV)