算法设计与分析复习——第三章:动态规划-阿里云开发者社区

开发者社区> 科技小能手> 正文

算法设计与分析复习——第三章:动态规划

简介:
+关注继续查看

 第三章:动态规划

1  分治算法和动态规划算法都是通过对问题进行分解,通过对子问题的求解然后进行解重构,从而实现对原问题的求解。请指出这两种算法在对问题进行分解时各自所遵循的原则。

答:分治算法对问题进行分解时所遵循的原则是将待求解问题分解为若干个规模较小、相互独立且与原问题相同的子问题(不包含公共的子问题)。

动态规划对问题进行分解时所遵循的原则是将待求解问题分解为若干个规模较小、相互关联的与原问题类似的子问题(包含公共的子问题),采用记录表的方法来保存所有已解决问题的答案,而在需要的时候再找出已求得的答案,避免大量的重复计算。

 

2  动态规划算法的本质是什么,请简要阐述。

答:动态规划的实质是分治思想解决冗余,动态规划算法是将问题分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。

 

3  如果一个问题可以利用动态规划算法求解,那么该问题应满足什么条件?

答:该问题具有最优子结构性质(一个问题的最优解包含其子问题的最优解)和无后效性(将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态).

 

4、动态规划算法的基本思想是什么?请简述动态规划算法主要设计步骤。

答:动态规划算法的基本思想是将待求解问题分解成若干个相互关联的与原问题类似的子问题,求解这些子问题,并保存子问题的答案,避免重复计算,然后从这些子问题的解得到原问题的解。

动态规划算法主要设计步骤:

1)找出最优解的性质,并刻画其结构特征;

2)递归地定义最优值;

3)以自底向上的方式计算出最优值;

4)根据计算最优值时得到的信息,构造最优解;

5,什么是备忘录方法?它同动态规划法相比主要不同点是什么?请指出动态规划法和备忘录方法各自的适用范围。(注:平常说的“动态规划”是自底向上的动态规划,“备忘录方法”是自顶向下的动态规划。)

答:备忘录方法是动态规划算法的变形,它通过分治思想对原问题进行分解,以存储子问题的解的方式解决冗余计算,并采用自顶向下的递归方式获取问题的最终解。

与动态规划算法的不同之处是动态规划算法的递归方式是自底向上递归求解,而备忘录方法的递归方式是自顶向下递归求解。

当一个问题的所有子问题都至少要解一次时,使用动态规划算法。

当子问题空间中的部分子问题不需要求解时,使用备忘录方法。

6,矩阵相乘算法目前最好的时间复杂度是多少?

答:目前矩阵乘法最好的时间复杂度是能做到On2.376

7,分治法与动态规划法之间的相同点是什么?不同之处在哪些方面?

答:与分治法类似,动态规划法 也是把问题一层一层地分解为规模逐渐减小的同类型的子问题。

动态规划法与分治法的一个重要的不同点在于,用分治法分解后得到的子问题通常都是相互独立的, 而用动态规划法分解后得到的子问题很多都是重复的。因此,对重复出现的子问题,只是在第一次遇到时才进行计算,然后把计算所得的结果保存起来;当再次遇到该子问题时,就直接引用已保存的结果,而不再重新求解。

例题:

1,

 

2,

 

3,动态0-1背包

public class  SF_Beibao_0_1{

 public static void main(String[]args){

          int []v={1,2,3,4,5,6,7};

          int []w={2,3,4,5,34,23,2};

          int []b={2,3,4,1,2,3,5};

          int c=45;

          int d=36;

          int [][][]m=new int[v.length][c+1][d+1];

          knapsack(v,w,b,c,d,m);

          System.out.println("输出最优解:"+m[1][c][d]);

          }

 public static void knapsack(int[]v,int[]w,int []b,int c,int d,int[][][]m){

          int n=v.length-1;

     int jMax=Math.min(w[n]-1,c);

     int kMax=Math.min(b[n]-1,d);

     for(int j=0;j<=jMax;j++)

                   for(int k=0;k<=kMax;k++)

                             m[n][j][k]=0;

     for(int j=w[n];j<=c;j++)

     for(int k=b[n];k<=d;k++)

                             m[n][j][k]=v[n];

     for(int i=n-1;i>1;i--){

                    jMax=Math.min(w[i]-1,c);

                    kMax=Math.min(b[i]-1,d);

                    for(int j=0;j<=jMax;j++)

         for(int k=0;k<=kMax;k++)

         m[i][j][k]=m[i+1][j][k];

                    for(int j=w[i];j<=c;j++)

         for(int k=b[i];k<=d;k++)

         m[i][j][k]=Math.max(m[i+1][j][k],m[i+1][j-w[i]][k-b[i]]+v[i]);

                    }

         m[1][c][d]=m[2][c][d];

    if(c>=w[1]&&d>=b[1])m[1][c][d]=Math.max(m[1][c][d],m[2][c-w[1]][d-b[1]]+v[1]);

         }

 public static void trackback(int[][][]m,int[]b,int[]w,int c,int d,int[]x){

          int n=w.length-1;

     for(int i=1;i<n;i++)

     if(m[i][c][d]==m[i+1][c][d])x[i]=0;

     else {x[i]=1;c-=w[i];d-=b[i];}

     x[n]=(m[n][c][d]>0)?1:0;

     }

 }

4,

 


本文转自 梦朝思夕 51CTO博客,原文链接:http://blog.51cto.com/qiangmzsx/802715


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
《数据结构和算法分析》具有O(logN)对数特点的三个基本算法
对分查找 给定一个整数X和整数A0,A1,…,AN-1,后者已经预先排序并存在内存中,求使得Ai=X的下标i,如果X不在数据中,则返回i=-1。 int BinarySearch (const ElementType A[], ElementType x, int N)...
633 0
结构化大数据分析平台设计
## 前言  任何线上系统都离不开数据,有些数据是业务系统自身需要的,例如系统的账号,密码,页面展示的内容等。有些数据是业务系统或者用户实时产生的,例如业务系统的日志,用户浏览访问的记录,系统的购买订单,支付信息,会员的个人资料等。
1188 0
《面向对象分析与设计》一3.7 例题
本节书摘来自华章出版社《面向对象分析与设计》一书中的第3章,第3.7节,作者 麻志毅,更多章节内容可以访问云栖社区“华章计算机”公众号查看
1694 0
PostgreSQL · 特性分析 · 统计信息计算方法
一条SQL在PG中的执行过程是: ----> SQL输入 ----> 解析SQL,获取解析后的语法树 ----> 分析、重写语法树,获取查询树 ----> 根据重写、分析后的查询树计算各路径代价,从而选择一条成本最优的执行树 ----> 根据执行树进行执行 ----> 获取结果并返回
1538 0
《算法设计编程实验:大学程序设计课程与竞赛训练教材》——3.3 积性函数的实验范例
本节书摘来自华章计算机《算法设计编程实验:大学程序设计课程与竞赛训练教材》一书中的第3章,第3.3节,作者:吴永辉,王建德著, 更多章节内容可以访问云栖社区“华章计算机”公众号查看。
1190 0
14491
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载