动态规划(01背包).ppt

贪心策略?贪心策略:在对问题求解时,总是做出在当前看来是最好的选择。?贪心策略适用的前提是:局部最优策略能导致产生全局最优解。?贪心策略接近人的日常思维,每次选当前最优的,但局部最优解未必能得到全局最优解,如 01 背包,每次选择价值/重量最大的,未必最优。动态规划( DP ) ?每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。(以后课程再慢慢理解) ?(1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的, 就称该问题具有最优子结构。?(理解:局部最优,全局也最优) ?(2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。?(理解:前事确定了,后事如何都影响不了前事,例如李启铭开车撞死人了,后来说了句我爸是李刚,也改变不了撞死人事实) ?(3) 有重叠子问题(个别辅导资料提到记忆化搜索):即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。?(理解:一般使用数组保存子问题结果,因为后面子问题的求解会用到前面子问题的结果,不用再重复计算,如走楼梯 f[n]:=f[n-1]+f[n-2] , 而不是使用递归函数 f(n):=f(n-1)+f(n-2) ) ? dfs (爆搜),从第二层开始每次有两条路可选,当层数 N = 100 时,路径条数 P = 2 99,这是一个非常大的数即使用世界上最快的电子计算机,也不能在短时间内计算出来。?贪心,每层选择最大值,例如 13-11-12-14-13 其路径的值为 63 ,但这不是最优解。?动态规划,如果得到一条由顶到底的某处的一条最佳路径, 那么对于该路径上的每一个中间点来说,由顶至该中间点的路径所经过的数字和也为最大。因此本题是一个典型的多阶段决策最优化问题。 13 11 12 6 12 87 14 7 26 15 13 8 24 11 ?数组 A[i,j] 保存三角形数塔, B[i,j] 保存状态值,按从上往下方式进行求解。 Var a,b : array[1..100,0..100] of word; i,j,n : byte; max : word; begin repeat write('N = '); readln(n); until n in [1..100]; fillchar(a,sizeof(a),0); b := a; for i := 1 to n do begin for j := 1 to i do read(a[i,j]); readln; end; b[1,1] := a[1,1]; for i := 2 to n do for j := 1 to i do if b[i-1,j-1] > b[i-1,j] then b[i,j] := b[i-1,j-1]+a[i,j] else b[i,j] := b[i-1,j]+a[i,j]; max := 0; for i := 1 to