рассчитать максимальную прибыль

[Spook]

Наконец-то решил.
mserg, интересно, отличаются ли фундаментально ЗЛП и динамическое программирование в плане решения? ЗЛП можно решить динамическим программированием, и также это очередной пример для меня задачи динамического программирования, решаемой методами линейного программирования. Думаю, что в плане сложности вычислений, ЗЛП может решаться чуть быстрее, но сложнее в реализации. Динамикой, как я посчитал, в этой задаче требуется $O(N^3)$ операций.

[mserg]

Линейное программирование решает ~70% задач инженерно-экономических задач, чего не скажешь о динамическом программировании. Это скорее экзотика, чем практичный метод решения задач. Пакеты решения линейных задач обычно имеют средства моделирования, среду разработки и отладки моделей, а также интерфейсы подключения к прикладным программам. Так, для решения Вашей задачи я написал аж 12 строк кода...

[Spook]

Интересно. А в какой среде работаете? В $MatLab$? Можете код в ЛС скинуть? Я написал эту программу в $MS$ $Visual$ $C$++ - получилось 173 строки кода. А что выдает Ваша программа на такие входные данные:
50 5
6 4 3 3 6 9 10 4 1 10 6 2 0 0 8 8 8 5 9 8 4 8 0 3 6 8 5 1 7 2 1 5 5 1 0 8 7 2 3 8 0 8 7 10 6 3 0 2 8 7
?

[mserg]

ответ <2,3,5,6,8> или <1,3,5,6,8> или <2,4,6,8,10> ... (оптимум 226). Решалось системой Quick NP.

[Spook]

Ух ты, даже три варианта! У меня последний получился. Почитал в интернете про $Quick$ $NP$ - крутая система, но довольно дорогая (вроде около 30к стоит по какойто старой ссылке). А Вы, видимо, принимали участие в ее разработке?