摘要算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
其中最常见的五中基本算法是递归与分治法、动态规划、贪心算法、回溯法、分支限界法。
本文通过这种算法的分析以及实例的讲解，让读者对算法有更深刻的认识，同时对这五种算法有更清楚认识关键词：算法，递归与分治法、动态规划、贪心算法、回溯法、分支限界法AbstractAlgorithm is the description to the problem solving scheme,a set of clear instructions to solve the problem and represents the describe the strategy to solve the problem using the method of system mechanism . That is to say, given some confirm import，the Algorithm will find result In a limited time。
If an algorithm is defective or is not suitable for a certain job, it is invalid to execute it. Different algorithms have different need of time or space, and it's efficiency are different.There are most common algorithms: the recursive and divide and conquer、dynamic programming method、greedy algorithm、backtracking、branch and bound method.According to analyze the five algorithms and explain examples, make readers know more about algorithm , and understand the five algorithms more deeply.Keywords: Algorithm, the recursive and divide and conquer, dynamic programming method, greedy algorithm、backtracking, branch and bound method目录1. 前言 (4)1.1 论文背景 (4)2. 算法详解 (5)2.1 算法与程序 (5)2.2 表达算法的抽象机制 (5)2.3 算法复杂性分析 (5)3．五中常用算法的详解及实例 (6)3.1 递归与分治策略 (6)3.1.1 递归与分治策略基本思想 (6)3.1.2 实例——棋盘覆盖 (7)3.2 动态规划 (8)3.2.1 动态规划基本思想 (8)3.2.2 动态规划算法的基本步骤 (9)3.2.3 实例——矩阵连乘 (9)3.3 贪心算法 (11)3.3.1 贪心算法基本思想 (11)3.3.2 贪心算法和动态规划的区别 (12)3.3.3 用贪心算法解背包问题的基本步骤： (12)3.4 回溯发 (13)3.4.1 回溯法基本思想 (13)3.3.2 回溯发解题基本步骤 (13)3.3.3 实例——0-1背包问题 (14)3.5 分支限界法 (15)3.5.1 分支限界法思想 (15)3.5.2 实例——装载问题 (16)总结 (18)参考文献 (18)1. 前言1.1 论文背景算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。
也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。
一个状态到另一个状态的转移不一定是确定的。
随机化算法在内的一些算法，包含了一些随机输入。
计算机的有限资源促使人们关注程序的执行性能，进而催生了计算机算法这一研究领域。
自上世纪60年代开始至今，已出现了大量解决不同问题的有效算法。
由于属于同一问题类的不同问题之间具有相似性，其解决算法也具有一定的共性，因此产生了一般的算法设计技术，如递归技术、分治、动态规划、贪心、图的遍历、回溯、分支限界等。
掌握算法、分析算法、将算法应用到其他领域、创造更高效的算法，是对每一个计算机学着的基本要求。
本文主要分析五中常用的算法（递归与分治法、动态规划、贪心算法、回溯发、分支限界发），以及对相应算法的实例详细讲解。
通过对五中常用算法的单独讲解、综合对比，分析出各种算法的特点以及适用领域，最后列举相应的算法实例，让读者对这五中常用算法有更深的了解。
2. 算法详解2.1 算法与程序算法：是满足下述性质的指令序列。
•输入：有零个或多个外部量作为算法的输入。
•输出：算法产生至少一个量作为输出。
•确定性：组成算法的每条指令清晰、无歧义。
•有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。
程序：是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质(4)即有限性。
2.2 表达算法的抽象机制1.从机器语言到高级语言的抽象高级程序设计语言的主要好处是：（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高2.抽象数据类型抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。
抽象数据类型带给算法设计的好处有：（1）算法顶层设计与底层实现分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。
2.3 算法复杂性分析算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。
这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。
如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。
一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)。
一般只考虑最坏情况、最好情况和平均情况下的复杂度。
3．五中常用算法的详解及实例3.1 递归与分治策略3.1.1 递归与分治策略基本思想任何一个可以用计算机求解的问题所需要的计算时间都与其规模有关，问题的规模越小，解题所需的时间往往越少，从而比较容易处理，但想直接解决一个较大的问题，有时是相当困难的。
分治法的设计思想，是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分解出来的子问题都可解，并且利用这些子问题的解求出原问题的解，那么这种分治法是可行的。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复使用分治手段，可以使子问题与原问题类型一致而规模却不断减小，最终使子问题缩小到很容易求出其解。
这样就自然导致递归算法的产生。
分治与递归像一对孪生兄弟，经常同时应用在算法设计中，并由此产生许多高效算法。
图3.1 递归与分治策略基本思想其中，|P|表示问题P的规模，n0为一阀值，表示问题P的规模不超过n0，问题已容易求解，不再分解。
Adhoc（P）是该分治法中的基本算法，用于直接解小规模的问题P。
因此，当P的规模不超过n0时，直接用算法Adhoc（P）求解。
算法Merge(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1，P2，P3,…,Pk合并为P的解。
3.1.2 实例——棋盘覆盖(1):问题描述在一个2k×2k（k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格，显然，特殊方格在棋盘中出现的位置有4k种情形，因而就有种不同的棋盘(如图3.2)。
图3.2 4×4棋盘格式棋盘覆盖问题要求用如图3.3所示的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
图3.3 4中L型骨牌(2)：算法实现棋盘覆盖问题中数据结构的设计：①棋盘：用二维数组Board[size][size]表示一个棋盘， Board[0][0]是棋盘的左上角方格。
其中size=2k。
为了在递归处理的过程中使用同一个棋盘，将数组Board设为全局变量；②子棋盘：在棋盘数组Board[size][size]中，由子棋盘左上角的下标tr、tc和棋盘边长s表示；③特殊方格：用Board[dr][dc]表示，dr和dc是该特殊方格在棋盘数组Board中的下标；④L型骨牌：一个4k的棋盘中有一个特殊方格，所以用到L型骨牌的个数为( -1)/3将所有L型骨牌从1开始连续编号，用一个全局整型变量tile表示，其初始值为0。
算法的输入参数是：tr:棋盘左上角方格的行号tc:棋盘左上角方格的列号dr:特殊方格所在的行号dc:特殊方格所在的列号(3)算法详细实现图3.4 棋盘覆盖算法本算法的时间复杂度为T（K）=O（4k）,需要骨牌个数为（4k-1）/3,是一个在渐进意义下的最优算法。
3.2 动态规划3.2.1 动态规划基本思想动态规划过程中，每次决策依赖于当前状态，又随即引起状态的转移。
一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。