动态规划.ppt

浅谈动态规划动态规划的基本模型动态规划的基本模型动态规划的基本模型动态规划的基本模型动态规划的基本模型动态规划的基本模型阶段：据空间顺序或时间顺序对问题的求解划分阶段。状态：描述事物的性质不同事物有不同的性质因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。决策：根据题意要求对每个阶段所做出的某种选择性操作。状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。动态规划的基本概念:动态规划的两个必要条件动态规划的两个必要条件动态规划的两个必要条件动态规划的基本概念:动态规划的基本概念:贪心法产生一个按贪心策略形成的判定序列该序列不保证解是全局最优的。而动态规划会产生许多判定序列再按最优性原理对这些序列加以筛选去除那些非局部最优的子序列。0/1背包问题———最简单的动态规划问题0/1背包问题———最简单的动态规划问题0/1背包问题———最简单的动态规划问题0/1背包问题———最简单的动态规划问题0/1背包问题———最简单的动态规划问题多多看DVD多多看DVD多多看DVD金明的预算方案金明的预算方案金明的预算方案for(i=1;i<=n;i++)for(j=1;j<=m;j++){f[i][j]=f[i-1][j];//一个也不选if(j>=w[i][0])//仅选择主件f[i][j]=max(f[i][j]f[i-1][j-w[i][0]]+c[i][0]);if(j>=w[i][0]+w[i][1])//选择主件后再选第择一个附件f[i][j]=max(f[i][j]f[i-1][j-w[i][0]-w[i][1]]+c[i][0]+c[i][1]);if(j>=w[i][0]+w[i][2])//选择主件后再选第择一个附件f[i][j]=max(f[i][j]f[i-1][j-w[i][0]-w[i][2]]+c[i][0]+c[i][2]);if(j>=w[i][0]+w[i][1]+w[i][2])//选择主件后再选择两个附件f[i][j]=max(f[i][j]f[i-1][j-w[i][0]-w[i][1]-w[i][2]]+c[i][0]+c[i][1]+c[i][2]);}最小重量机器设计最小重量机器设计最小重量机器设计最小重量机器设计拦截导弹问题———最长单调不上升序列拦截导弹问题———最长单调不上升序列拦截导弹问题———最长单调不上升序列拦截导弹问题———最长单调不上升序列拦截导弹问题———最长单调不上升序列拦截导弹问题———最长单调不上升序列尼克的任务尼克的任务尼克的任务尼克的任务尼克的任务添括号问题———资源分配类动态规划添括号问题———资源分配类动态规划机器分配机器分配机器分配机器分配加分二叉树———区间类动态规划加分二叉树———区间类动态规划加分二叉树———区间类动态规划加分二叉树———区间类动态规划加分二叉树加分二叉树加分二叉树加分二叉树石子归并问题石子归并问题石子归并问题石子归并问题石子归并问题