下载文档原格式
吉林师范大学计算机学院案教)(算法部分称C 程序设计课程名系级院级计算机学院计算机科学与技术095101 系、实验室() 计算机基础教研室教研室计算机科学与技术3班班级09 授课郑言生实习滕国文导教师系指吉林师范大学计算机学院二○一二年四月二十五日（星期三5，6节）课型章节：动态规划基本思想基要本参教考材资和料主：算法设计与分析》教学目的：本课程以C语言为教授程序设计的描述语言，结合语言介绍程序设计的基本原理、技巧和方法。
主要讲授内容包括程序设计动态规划基本概念，动态规划的基本步骤，动态规划问题的特。
通过本课程的学习，为算法更好的学习，以及能用计算机解决一些实际问题打下坚实的征基础。
教学基本要求：掌握C语言中动态规划的基本概念，。
并能熟练使动态规划的基本步骤，动态规划问题的特征用C语言动态规划思想解决一些简单程序问题；掌握一些基本算法结构及相关方法；熟悉程序设计的思想和编程技巧。
重点：动态规划基本概念，。
动态规划的基本步骤，动态规划问题的特征难点:动态规划的基本步骤课型：理论课教法：1.多媒体讲解2.举例讲解教学内容及过程：1.课前回顾：枚举法: 在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这结论是可靠的，这种归纳方法叫做枚举法．2. 数塔问题有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。
简单的进行选举方法的引导，让同学们主动思考到动态规划的思想上了。
考虑一下：从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。
同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。
这样一层一层推下去，直到倒数第二层时就非常明了。
如数字2，只要选择它下面较大值的结点19前进就可以了。
所以实际求解时，可从底层开始，层层递进，最后得到最大值。
运筹学教案动态规划一、引言1.1 课程背景本课程旨在帮助学生掌握运筹学中的动态规划方法，培养学生解决实际问题的能力。
1.2 课程目标通过本课程的学习，学生将能够：（1）理解动态规划的基本概念和原理；（2）掌握动态规划解决问题的方法和步骤；（3）能够应用动态规划解决实际问题。
二、动态规划基本概念2.1 定义动态规划（Dynamic Programming，DP）是一种求解最优化问题的方法，它将复杂问题分解为简单子问题，并通过求解子问题的最优解来得到原问题的最优解。
2.2 特点（1）最优子结构：问题的最优解包含其子问题的最优解；（2）重叠子问题：问题中含有重复子问题；（3）无后效性：一旦某个给定子问题的解确定了，就不会再改变；（4）子问题划分：问题可以分解为若干个子问题，且子问题之间是相互独立的。
三、动态规划解决问题步骤3.1 定义状态状态是指某一阶段问题的一个描述，可以用一组变量来表示。
3.2 建立状态转移方程状态转移方程是描述从一个状态到另一个状态的转换关系。
3.3 确定边界条件边界条件是指初始状态和最终状态的取值。
3.4 求解最优解根据状态转移方程和边界条件，求解最优解。
四、动态规划应用实例4.1 0-1背包问题问题描述：给定n个物品，每个物品有一个重量和一个价值，背包的最大容量为W，如何选择装入背包的物品，使得背包内物品的总价值最大。
4.2 最长公共子序列问题描述：给定两个序列，求它们的最长公共子序列。
4.3 最短路径问题问题描述：给定一个加权无向图，求从源点到其他各顶点的最短路径。
5.1 动态规划的基本概念和原理5.2 动态规划解决问题的步骤5.3 动态规划在实际问题中的应用教学方法：本课程采用讲授、案例分析、上机实践相结合的教学方法，帮助学生深入理解和掌握动态规划方法。
教学评估：课程结束后，通过课堂讨论、上机考试等方式对学生的学习情况进行评估。
六、动态规划算法设计6.1 动态规划算法框架介绍动态规划算法的基本框架，包括状态定义、状态转移方程、边界条件、计算顺序等。
