Требуется составить оптимальный план и вычислить максимальную прибыль.
Дано T единиц времени и n задач
последующие n строк содержат два натуральных числа (xi, yi) - время, необходимое на выполнение задачи, и прибыль, которую можно получить, выполнив её.
Оптимальный план обладает двумя свойствами:
- Суммарное время, затраченное на выполнение задач, включённых в план, не превышает T.
- Суммарная прибыль от выполнения этих задач была максимальна.
Например при входных данных:
10 3
8 100
3 10
3 10
Максимальная прибыль:
100 (задача 1)
Пример 2:
10 4
5 10
5 20
2 5
2 6
Максимальная прибыль:
31 (задачи 2,3,4)
Подтолкните к решению, посоветуйте что почитать (но не целиком книгу, а отдельную тему, Shen'я с Виртом я уже копаю в поисках подобных задач). Я просто ещё не сталкивался с подобными задачами и хочу её решить, просто для себя.
Простой
Средний