主题:能不能讲讲动态规划啊?
jdxyw
[专家分:230] 发布于 2006-05-27 21:23:00
能不能讲讲动态规划啊?书上都是数学推导,看不懂……举的例子又没有说明,看的很痛苦……那位好心人能不能讲一讲,举个详细的例子啊?谢谢啊!
回复列表 (共5个回复)
沙发
lanyuewei [专家分:60] 发布于 2006-05-27 22:52:00
那我就简单说一下吧.
动态规划就是列也所有可能的方案,然后选出最优解.
比如一个人最多能拿得动100斤,现有40,50,70斤各一袋黄金.
就有如下方案:
1 40+50=90
2 70
90>70,所以选一袋40斤和一袋50斤.
板凳
jdxyw [专家分:230] 发布于 2006-05-27 22:57:00
有没有编程的例子啊?
3 楼
rickone [专家分:15390] 发布于 2006-05-27 23:22:00
1楼的解释得也太简单了吧
动态规划都用于最优化问题,如果一个最优化问题可以分成k步完成,对于第i步,可以由前面的结果找出当前最优解,并最终找出全局最优解,这样的方法就是动态规划.书上有比我更严格好的定义.对于每一步都有一个状态,相临状态之前有状态转移方程,一般方程中都有min{}或max{},表示求当前最优解.一般用DP解出来的都需要O(n*n)的复杂度.
大致这样,有误请指出.
4 楼
euc [专家分:4310] 发布于 2006-05-28 11:54:00
我对DP的理解,它就像是步步为营,想扎营十里,必须从眼前开始一座一座地扎,最后才能扎到十里。还是不懂?-_-||
5 楼
蹦蹦的笨笨 [专家分:430] 发布于 2006-05-29 10:28:00
动态规划在数据结构书中哪一章讲的啊?没找到,我的是严蔚敏的书
我来回复