[理学]第10章_程序设计基础.ppt

问题求解模式 动态规划所处理的问题是一个多阶段决策问题， 一般由初始状态开始，通过对中间阶段决策的选择， 达到结束状态。这些决策形成了一个决策序列，同时 确定了完成整个过程的一条活动路线（通常是求最优 的活动路线）。  初始状态→决策１→决策２→…→决策ｎ→结束状态 动态规划的设计有一定的模式，一般要经历以下步骤： (1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，要注意划分后的阶段是有序或可排序的，否则问题无法求解。 (2)确定状态和状态变量：将问题发展到各个阶段时所处的各种情况用不同的状态表示出来。当然，状态的选择要满足无后向性。 (3)确定决策并写出状态转移方程：状态转移就是根据上一阶段的状态和决策导出本阶段的状态。如果确定了决策，状态转移方程很容易写出。但事实上常常反过来做，根据相邻状态之间的关系来确定决策。 (4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。 多级图问题(multistage graph problem)： G = ( V, E ) 如下5级图：5个不相交的结点集合 Vi , i=1,2,3,4,5。 V1 及 V5 分别只有一个结点，称之为 源点S 和 汇点T 。 寻找一条从 S 到 T 的最小耗费路径（同一级结点内无边连接）。 向前法 向后法 √ 向前法 cost(i,j) = MIN { c(j,k) + cost(i+1,k) } cost(i,j)表示第i级上结点j到汇点T的最小耗费路径 c(j,k)表示结点j到k的耗费 目标：求cost(1,1) cost(4,9) = 4; cost(4,10) = 2; cost(4,11) = 5 cost(3,6) = MIN{ c(6,9) + cost(4,9); c(6,10) + cost(4,10) } = 7 cost(3,7) = MIN{ c(7,9) + cost(4,9); c(7,10) + cost(4,10) } = 5 cost(3,8) = MIN{ c(8,10) + cost(4,10); c(8,11) + cost(4,11) } = 7 cost(2,2) = MIN{ c(2,6) + cost(3,6); c(2,7) + cost(3,7); c(2,8) + cost(3,8) } = 7 cost(2,3) = 9; cost(2,4) = 18; cost(2,5) = 15 cost(1,1) = MIN{ c(1,2) + cost(2,2); c(1,3) + cost(2,3) ; c(1,4) + cost(2,4); c(1,5) + cost(2,5) } = 16 记录路径： 1 2 3 4 5 6 7 8 9 10 11 12 2 7 6 8 8 10 10 10 12 12 12 ∧ 贪心法与动态规划法的差别： 贪心法：自顶向下，产生一个按贪心策略形成的判定序列，该序列不保证解是全局最优的。 　　动态规划：自底向上，会产生许多判定序列，再按最优化原理对这些序列加以筛选，去除那些非局部最优的子序列。 设 f (n,w) 表示前 n 个物品装 w 公斤重时的最大价值， wi为第 i 个物品的重量，vi 为第 i 个物品的价值，则 递推公式为: ? f (i,w) = max { f(i-1,w), f(i-1,w-wi)+vi } 用动态规划方法求解背包问题： …… #define LIMIT 8 // 重量限制 #define N 5 // 物品种类 #define MIN 1 // 最小重量 struct body { char name[20]; int size; int price; }; typedef struct body object; int main() { int item[LIMIT+1] = {0}; int value[LIMIT+1] = {0}; int newvalue, i, s, p; object a[]