Максимальный вес совместимых временных интервалов
Выбрать непересекающиеся полуоткрытые интервалы с максимальной суммой весов и показать динамическое сравнение включения и пропуска.
Ваш пример
Разбор примера
Максимальный вес = 9
| Интервал | Совместимый префикс | Взять | Пропустить | Лучшее |
|---|---|---|---|---|
| 2 | 0 | 3 | 0 | 3 |
| 1 | 0 | 5 | 3 | 5 |
| 3 | 1 | 7 | 5 | 7 |
| 4 | 3 | 9 | 7 | 9 |
- Полуоткрытые интервалы разрешают следующий старт точно в момент окончания предыдущего.
- Каждая строка динамики сравнивает включение с лучшим совместимым префиксом и пропуск.
Метод и условия расчёта
Интервалы [начало,конец) с общим концом совместимы.
После сортировки по окончанию DP[j]=max(DP[j−1],wⱼ+DP[p(j)]).
Теория к методу
Для взвешенного расписания сортируют интервалы по окончанию и сравнивают два решения: пропустить текущую задачу или взять её вместе с лучшим совместимым префиксом. Таблица хранит лучший вес, а обратные решения восстанавливают набор задач.
Сначала определите смысл границы. Полуоткрытый интервал [a,b) занимает время a, но освобождает ресурс в момент b. Поэтому задача, начинающаяся точно в b, совместима с предыдущей. Каждому интервалу нужен собственный вес: это может быть доход, полезность или число баллов. Он не обязан совпадать с длительностью.
Пример: Пусть задачи заданы как (начало,конец,вес): (0,3,5), (1,2,3), (2,4,4), (4,5,2). Первая задача с последней дают вес семь; задачи 2,3,4 дают девять.
Оптимальный вес равен девяти, выбранные исходные номера — 2,3,4. Общие точки времени два и четыре разрешены договорённостью о полуоткрытых интервалах.
Вопросы по теме
Кратчайший интервал всегда выгоднее?
Нет. При весах важна сумма ценностей совместимого набора, а не только количество интервалов.
Нужно брать отрицательный вес?
Нет. Пустой набор разрешён, поэтому отрицательная цель не навязывается.
Методы алгоритмов: углубление: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.