Поскольку это, вероятно, проблема с домашней работой, я не буду давать точную реализацию, но я подробно опишу алгоритм:
Во-первых, мы должны отсортировать список ввода по крайнему сроку, поэтому домашнюю работу с самый низкий крайний срок - в начале списка, а домашняя работа с самым высоким крайним сроком - в конце.
Затем мы определяем dp(i, t), где i - индекс домашней работы, которую мы учитывая, что t - это время, потраченное на следующее:
- Если
i - последний элемент домашней работы (в основном n - 1), то мы возвращаем 0, если не можем выполнить домашнюю работу вовремя (t + hw[i].time > hw[i].deadline), в противном случае мы возвращаем счет за домашнее задание. - Если
i не последний элемент домашнего задания, если мы не можем выполнить домашнее задание вовремя, мы возвращаем dp(i + 1, t). - Если
i не является последним домашним заданием, и мы можем выполнить домашнее задание вовремя, тогда мы возвращаем max(dp(i + 1, t), dp(i + 1, t + hw[i].time) + hw[i].score).
Этот алгоритм возвращает только общий балл, но вы может легко изменить его, чтобы вернуть кортеж, содержащий общую оценку и вектор домашних заданий.