проблема взвешенного интервала с динамическим программированием

Question

Я имею дело с проблемой взвешенного интервала.В традиционной формулировке у нас есть список {i_1, ..., i_n} заданий с весами w_j.Я нашел довольно простой подход с примером из книги «Разработка алгоритмов» Кляйнберга и Тардоса, где динамическое программирование основано на первоначальной сортировке интервалов по времени окончания (https://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/06dynamic-programming.pdf). Алгоритм использует концепцию p_j (предшественник), которая является самой большой работой, я не конфликтую с работой j. В моем конкретном случае, однако, я сталкиваюсь с проблемой, когда есть несколько работ с одинаковым временем окончания, поэтому у меня будет несколько p_js. Из-за этого яЯ не уверен, насколько прямым или подходящим был бы этот подход DP для моей проблемы. У вас есть какие-либо предложения?

Answer 1

Обратите внимание, что вам нужно заказывать задания, используя оператор <=, а не <:

Для этой формулы не имеет значения,у вас есть несколько заданий с одинаковым временем окончания.

p(j) - это индекс с наибольшим индексом среди заданий с одинаковым временем окончания.