2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 
Сообщение04.03.2009, 17:04 
Аватара пользователя
Интересно. А в какой среде работаете? В $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
?

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

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

 
 
 [ Сообщений: 20 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group