Максимальный вес совместимых временных интервалов

Выбрать непересекающиеся полуоткрытые интервалы с максимальной суммой весов и показать динамическое сравнение включения и пропуска.

Ваш пример

Числа и дроби: 0.5, 0,5 или 1/3. Числа в строке разделяются пробелами, строки — переносом. Выражения не выполняются.

Разбор примера

Максимальный вес = 9

Проверяемые промежуточные данные
ИнтервалСовместимый префиксВзятьПропуститьЛучшее
20303
10535
31757
43979
  1. Полуоткрытые интервалы разрешают следующий старт точно в момент окончания предыдущего.
  2. Каждая строка динамики сравнивает включение с лучшим совместимым префиксом и пропуск.

Метод и условия расчёта

Интервалы [начало,конец) с общим концом совместимы.

После сортировки по окончанию 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. По ссылкам можно сверить определения и условия модели.