Ответ 1
Это проблема динамического программирования. Предположим для простоты, что все прибыли неотрицательны.
Определите F(i, j) как максимальную прибыль, которая должна быть сделана при планировании i 'th работы и всех вещей, которые зависят от нее (рекурсивно вниз), на или позже, чем j' th second, или -1, если это невозможно.
Тогда F(i, j) есть -1, если F(i_1, j+1) равно -1 для любой зависимости i_1 от i. В противном случае он больше (F(i, j) плюс сумма F(i_1, j+1)) или F(i, j+1).
И тогда ваш ответ представляет собой сумму F(i, 0) для всех заданий i без зависимостей.
(Без неограниченных машин эта проблема станет np-hard...)
Вот пример того, как использовать вашу проблему для моделирования уравнений MAX-SAT, где каждое предложение имеет все условия, которые не сбрасываются, или все термины отрицаются.
Предположим, что у нас есть 4 булевых переменных A, B, C и D. В качестве примера предположим, что мы хотим выполнить максимальную выполнимость для уравнения (A && B) || (!A && !C) || (!B && !C && !D) || (C && D). (Где ! означает нет, && означает и, и || означает или.)
Используйте обозначения J1 > J2 для заданий, в которых J1 должен выполняться до J2. И распределите по круглым скобкам так, чтобы J1 > (J2, J3) означало, что J1) is a dependency for both J2 and J3`.
Теперь, чтобы смоделировать булевы, задайте 12 заданий. A1 > A2 > A3, B1 > B2 > B3, C1 > C2 > C3 и D1 > D2 > D3. Тогда задание A2, B2, C2, D2 должно происходить в момент времени 2 или 3, а логическое A - это истина утверждения "A2 происходит во время 2". А также для других логических объектов.
Все эти задания получают прибыль 1 независимо от того, в какое время они работают. Мы ввели 3x столько заданий, как booleans, но пока это просто.
Теперь добавьте задания для предложений. Каждое из этих заданий будет иметь прибыль 11, если оно работает в секундах 2 или 3 и 1 в противном случае. Таким образом, ваша максимальная прибыль будет достигнута, если вы найдете настройки для своих логических элементов, которые максимизируют количество условий, которые являются истинными.
(A2, B2) > J1 моделирует истину (A && B).
J2 > (A2, C2)) моделирует истину (!A && !C).
J3 > (B2, C2, D2) моделирует истину (!B && !C && !D).
(C2, D2) > J4 моделирует истину (C && D).
Это снова простое преобразование с добавлением количества заданий, равным количеству предложений.
Итак, мы моделируем проблемы MAX-SAT с планированием. Но мы не можем имитировать все. В частности, мы не можем моделировать предложения со смешанным отрицанием типа (A && !B). Таким образом, хотя MAX-SAT NP-жесткий, возможно, что эта ограниченная версия не является. Однако другие ограниченные версии MAX-SAT, например MAX-2SAT, имеют тенденцию быть NP-жесткими, и это моя интуиция, что это тоже будет.
Но для доказательства или опровержения этой интуиции вы должны спросить на более подходящем форуме. Как https://cs.stackexchange.com/.