Как решать подобные задачи (поиск максимальной прибыли)?

Question

[Евгений Иванович]

Требуется составить оптимальный план и вычислить максимальную прибыль.
Дано 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'я с Виртом я уже копаю в поисках подобных задач). Я просто ещё не сталкивался с подобными задачами и хочу её решить, просто для себя.

Comments

[Виталий Витренко]

Одну задачу можно повторять несколько рас?

Answer 1

[SeptiM]

https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...

Comments

[Евгений Иванович]

Вот, именно это я и искал. Огромное спасибо, добра вам)

[SeptiM]

=)

Answer 2

[Виталий Витренко]

Самая обычная задача целочисленного программирования(вообще не связано с обычным программированием).
Любая такая задача сводится к целевой функции, которую нужно максимизировать или минимизировать и ограничениям которые должны выполнятся.
В вашем случае(пример 1) целевая функция:
100х₁ + 10х₂+10х₃ -> max (т.е. нужно максимизировать сумму, х_i в данном случае - сколько рас выполняется задача).
А ограничение:
8х₁ + 3х₂+3х₃ <= 10;
х_i - целые;
//если одна задача может выполнятся только один рас, то дополнительное ограничение: х_i = {1, 0}.
Для нахождения решения в ручную есть несколько методов, наиболее универсальный - симплекс метод.
Можно посчитать в экселе с помощью "поиска решений". Для серьезных задач с большим кол-вом переменных существуют специальные solver, например Gurobi.

Answer 3

[kazmiruk]

Помнится в универе нас гоняли подобными задачами. Предмер теория игр, тема максимальные и минимальные стратегии

Comments

[Евгений Иванович]

спасибо, буду гуглить. ^^

[kazmiruk]

Евгений Иванович: Погуглите все таки вариант brainick так как это все таки линейное программирование :) Я ошибся похоже