下载文档原格式
算法设计与分析■期末考试题整理1、一个算法应有哪些主要特征？又穷性，确定性，可行性，0个或多个输入，一个或多个输岀2、分治法(Divide and Conquer)与动态规划(Dynamic Programming)有什么不同？分治算法会重复的求解公共了问题，会做许多不必要的T作，而动态规划对每个了问题Z 求解一次，将其结果存入一张表屮，从而避免了每次遇到各个了问题有从新求解。
3、试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。
贪心算有效性：最小生成树、哈弟曼、活动安排、单元最短路径。
无效反例：0——I背包问题，无向图找嚴短路径问题。
4、求解方程fi[l)=f(2)=l。
由f(n)=f(n-1 )+f(n-2) nJ'得f(n)-f(n-l)-f(n-2)=0M得方程的特征方程为/ _兀一1 = 0,设特征方程的2个根本分别为"，兀2,则可得尤]=心=匕二2,则有- 21 4- V5 … 1 — yl~5 n/S) = C|(—y—) +C2(—y—)乂/•⑴= .f(2) “可得可得C] = a,c2 = hf(n) = a(^y+b(^)5、求解方稈T(n)=2T(n/2)+l, T(l)=l,设尸2匚r(n) = 2r(n/2) + l2T(n/2) = 22T(n/22) + 222T(/7/22)=23T(A?/23)+222iTS/2z) = 25S/2*) + 2"T上面所有式子相加，相消得T(n) = 2*7(1) + 2°+2,+22 + + 2^ -J-2*=2k +1* --------1-2=2A+, -16、编写一个Quick Sorting算法，并分析时间复杂性。
int part(int *a,int p,int r){int i,j,x,t;x=a[r];i=p-l；fbrOP；jv=r・l；j40{if(aU]<=x){汁+；t=a[i];a[i]=a[j]；aU]=t；}}t=a[i+l]；a[i+l]=a[r];a[r]=t;return 汁1;}void quicksort(int *a,int p,int r){intq;if(pvr){q=part(a,p,r);quicksort(a,p,q-l);quicksort(a,q+l,r);}快速排序时间复杂度最坏情况为OS?),平均为O(nlogn);7、利用Quick Sorting的原理，编写一个查找第k小元索的算法。
1、二分搜索算法是利用（ A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（ A ）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（ A ）的一搜索方式。
A、分支界限法B、动态规划法C、贪心法D、回溯法4、在下列算法中有时找不到问题解的是（ B ）。
A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法5. 回溯法解旅行售货员问题时的解空间树是（ A ）.A、子集树B、排列树C、深度优先生成树D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是( B ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是（C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短8、以下不可以使用分治法求解的是（D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题9。
实现循环赛日程表利用的算法是（ A ）.A、分治策略B、动态规划法C、贪心法D、回溯法10、下列随机算法中运行时有时候成功有时候失败的是（C )A 数值概率算法B 舍伍德算法C 拉斯维加斯算法D 蒙特卡罗算法11．下面不是分支界限法搜索方式的是（ D ）。
A、广度优先B、最小耗费优先C、最大效益优先D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）.A、备忘录法B、动态规划法C、贪心法D、回溯法13.备忘录方法是那种算法的变形。
（ B )A、分治法B、动态规划法C、贪心法D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B )。
A、O（n2n)B、O（nlogn)C、O(2n）D、O(n）15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）.A、最小堆B、最大堆C、栈D、数组16．最长公共子序列算法利用的算法是（ B ）。
A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（ A ）.A、分治法B、动态规划法C、贪心法D、回溯法18.下面是贪心算法的基本要素的是（ C ）。
《算法设计与分析》历年期末试题整理(含答案)（1）用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程（3）算法的三要素1、操作2、控制结构3、数据结构算法具有以下5 个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义。
不存在二义性。
只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。
一般这两者与问题的规模有关。
经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。
利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。
在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
二、建立迭代关系式。
所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。
迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。
三、对迭代过程进行控制。
在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。
不能让迭代过程无休止地重复执行下去。
算法设计与分析期末试卷A卷A卷一、选择题1.二分搜索算法是利用（A）实现的算法。
A、分治策略2.回溯法解旅行售货员问题时的解空间树是（A）。
A、子集树3.下列算法中通常以自底向上的方式求解最优解的是（B）。
B、动态规划法4．下面不是分支界限法搜索方式的是（D）。
D、深度优先5．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为(。
B。
)。
B、O（nlogn）6．分支限界法解最大团问题时，活结点表的组织形式是（B）。
B、最大堆7、下面问题（B）不能使用贪心法解决。
B N皇后问题8.下列算法中不能解决0/1背包问题的是（A）A贪心法9.背包问题的贪心算法所需的计算时间为（B）A、O （nlogn）B、O（nlogn）10.背包问题的贪心算法所需的计算时间为（B）。
B、O（nlogn）二、填空题1.算法的复杂性有时间复杂性和空间复杂性之分。
2.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有穷性四条性质。
其中算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。
3.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是回溯法，需要排序的是动态规划和分支限界法。
4.动态规划算法的两个基本要素是最优子结构性质和重叠子问题性质。
5.回溯法是一种既带有深度优先搜索又带有回溯的搜索算法；分支限界法是一种既带有广度优先搜索又带有回溯的搜索算法。
6.用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。
在任何时刻，算法只保存从根结点到当前扩展结点的路径。
如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。
7.用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时O(n)。
Bool Color::OK(int k)for(int j=1;j<=n;j++)if((a[k][j] == 1) && (x[j] == x[k])) {return false;return true;8.用回溯法解布线问题时，求最优解的主要程序段如下。
A卷一、选择题1.二分搜索算法是利用（A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2. 回溯法解旅行售货员问题时的解空间树是（ A ）。
A、子集树B、排列树C、深度优先生成树D、广度优先生成树3.下列算法中通常以自底向上的方式求解最优解的是（B ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法4．下面不是分支界限法搜索方式的是（ D ）。
A、广度优先B、最小耗费优先C、最大效益优先D、深度优先5．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为 ( B ) 。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）6．分支限界法解最大团问题时，活结点表的组织形式是（ B）。
A、最小堆B、最大堆C、栈D、数组7、下面问题（B ）不能使用贪心法解决。
A 单源最短路径问题B N皇后问题C 最小花费生成树问题D 背包问题8.下列算法中不能解决0/1背包问题的是（A ）A 贪心法B 动态规划C 回溯法D 分支限界法9.背包问题的贪心算法所需的计算时间为（ B ）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）10.背包问题的贪心算法所需的计算时间为（B ）。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）二、填空题1.算法的复杂性有复杂性和复杂性之分。
2.算法是由若干条指令组成的有穷序列，且要满足输入、、确定性和四条性质。
其中算法的“确定性”指的是组成算法的每条是清晰的，无歧义的。
3.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是，需要排序的是，。
4.动态规划算法的两个基本要素是. 性质和性质。
5.回溯法是一种既带有又带有的搜索算法；分支限界法是一种既带有又带有的搜索算法。
6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。
在任何时刻，算法只保存从根结点到当前扩展结点的路径。
《算法分析与设计》期末试题及参考答案《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？1.确定性、可行性、输入、输出、有穷性2.2.算法分析的目的是什么？2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。
3.3.算法的时间复杂性与问题的什么因素相关？3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。
4.算法的渐进时间复杂性的含义？4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。
时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。
5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。
最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max{ T(n，I) } , I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n) =∑P(I)T(n，I) I∈Dn6.简述二分检索（折半查找）算法的基本过程。
6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]<="">7.背包问题的目标函数和贪心算法最优化量度相同吗？7. 不相同。
目标函数：获得最大利润。
最优量度：最大利润/重量比。
8.采用回溯法求解的问题，其解如何表示？有什么规定？8. 问题的解可以表示为n元组：（x1,x2,……x n），x i∈S i, S i为有穷集合，x i∈S i, （x1,x2,……x n）具备完备性，即（x1,x2,……x n）是合理的，则（x1,x2,……x i）(i<n)一定合理。
《算法分析与设计》期末复习题一、选择题1.应用Johnson 法则的流水作业调度采用的算法是（D ）A. 贪心算法B. 分支限界法C.分治法D. 动态规划算法2.Hanoi 塔问题如下图所示。
现要求将塔座A 上的的所有圆盘移到塔座B 上，并仍按同样顺序叠置。
移动圆盘时遵守Hanoi 塔问题的移动规则。
由此设计出解Hanoi 塔问题的递归算法正确的为：（B ）Hanoi 塔A. void hanoi(int n, int A, int C, int B) { if (n > 0) {hanoi(n-1,A,C, B); move(n,a,b);hanoi(n-1, C, B, A); } B. void hanoi(int n, int A, int B, int C) {if (n > 0) {hanoi(n-1, A, C, B); move(n,a,b);hanoi(n-1, C, B, A); }C. void hanoi(int n, int C, int B, int A) {if (n > 0) {hanoi(n-1, A, C, B); move(n,a,b);hanoi(n-1, C, B, A); }3. 动态规划算法的基本要素为（C）A. 最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D. 预排序与递归调用4. 算法分析中，记号O表示（B），记号Ω表示（A），记号Θ表示（D）。
A.渐进下界B.渐进上界C.非紧上界D.紧渐进界E.非紧下界5. 以下关于渐进记号的性质是正确的有：（A）A.f(n)(g(n)),g(n)(h(n))f(n)(h(n))=Θ=Θ⇒=ΘB. f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n))==⇒=C. O(f(n))+O(g(n)) = O(min{f(n),g(n)})D. f(n)O(g(n))g(n)O(f(n))=⇔=6.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）A. 最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D. 预排序与递归调用7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。
《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？1. 确定性、可行性、输入、输出、有穷性2.2.算法分析的目的是什么？2. 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。
3.3.算法的时间复杂性与问题的什么因素相关？3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。
4.算法的渐进时间复杂性的含义？4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。
时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。
5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。
最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max{ T(n，I) } , I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n) =∑P(I)T(n，I) I∈Dn6.简述二分检索（折半查找）算法的基本过程。
6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]<x，则A[i：(i+j)/2-1]找x，否则在A[ (i+j)/2+1：j] 找x。
上述过程被反复递归调用。
7.背包问题的目标函数和贪心算法最优化量度相同吗？7. 不相同。
目标函数：获得最大利润。
最优量度：最大利润/重量比。
8.采用回溯法求解的问题，其解如何表示？有什么规定？8. 问题的解可以表示为n元组：（x1,x2,……x n），x i∈S i, S i为有穷集合，x i∈S i, （x1,x2,……x n）具备完备性，即（x1,x2,……x n）是合理的，则（x1,x2,……x i）(i<n)一定合理。
《算法设计与分析》历年期末试题整理(含答案)（1）用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程（3）算法的三要素1、操作2、控制结构3、数据结构算法具有以下5 个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义。
不存在二义性。
只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。
一般这两者与问题的规模有关。
经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。
利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。
在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
二、建立迭代关系式。
所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。
迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。
三、对迭代过程进行控制。
在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。
不能让迭代过程无休止地重复执行下去。
迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。
对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。
编写计算斐波那契（Fibonacci）数列的第n 项函数fib（n）。
斐波那契数列为：0、1、1、2、3、……，即：fib(0)=0; fib(1)=1;fib(n)=fib(n-1)+fib(n-2) （当n>1时）。
写成递归函数有： intfib(int n){ if (n==0) return 0; if (n==1)return 1;if (n>1) return fib(n-1)+fib(n-2);}一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。
如果所有的兔子都不死去，问到第12 个月时，该饲养场共有兔子多少只？分析：这是一个典型的递推问题。
我们不妨假设第 1 个月时兔子的只数为 u 1 ，第 2 个月时兔子的只数为 u 2 ，第 3 个月时兔子的只数为 u 3 ，……根据题意，“这种兔子从出生的下一个月开始，每月新生一只兔子”，则有u 1 ＝ 1 ， u 2 ＝ u 1 ＋ u 1 × 1 ＝ 2 ， u 3 ＝ u 2 ＋ u 2 × 1 ＝4 ，……根据这个规律，可以归纳出下面的递推公式：u n ＝ u n － 1 × 2 (n ≥ 2)对应 u n 和 u n － 1 ，定义两个迭代变量 y 和 x ，可将上面的递推公式转换成如下迭代关系：y=x*2x=y让计算机对这个迭代关系重复执行 11 次，就可以算出第 12 个月时的兔子数。
参考程序如下：cls分而治之法1、分治法的基本思想 x=1 for i=2 to 12 y=x*2 x=y next i print y end任何一个可以用计算机求解的问题所需的计算时间都与其规模N 有关。
问题的规模越小，越容易直接求解，解题所需的计算时间也越少。
例如，对于n 个元素的排序问题，当n=1 时，不需任何计算；n=2 时，只要作一次比较即可排好序；n=3 时只要作3 次比较即可，…。
而当n 较大时，问题就不那么容易处理了。
要想直接解决一个规模较大的问题，有时是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
3、分治法的基本步骤分治法在每一层递归上都有三个步骤：（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；（3）合并：将各个子问题的解合并为原问题的解。
快速排序在这种方法中， n 个元素被分成三段（组）：左段 l e f t，右段 r i g h t 和中段 m i d d l e。
中段仅包含一个元素。
左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。
因此 l e f t 和 r i g h t 中的元素可以独立排序，并且不必对 l e f t 和 r i g h t 的排序结果进行合并。
m i d d l e 中的元素被称为支点( p i v o t )。
图 1 4 - 9 中给出了快速排序的伪代码。
/ /使用快速排序方法对 a[ 0 :n- 1 ]排序从 a[ 0 :n- 1 ]中选择一个元素作为 m i d d l e，该元素为支点把余下的元素分割为两段 left 和 r i g h t，使得 l e f t 中的元素都小于等于支点，而 right 中的元素都大于等于支点递归地使用快速排序方法对left 进行排序递归地使用快速排序方法对right 进行排序所得结果为 l e f t + m i d d l e + r i g h t考察元素序列[ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ]。
假设选择元素 6 作为支点，则 6 位于 m i d d l e； 4，3，1，5，2 位于 l e f t；8，7 位于 r i g h t。
当 left 排好序后，所得结果为 1，2，3，4， 5；当 r i g h t 排好序后，所得结果为 7，8。
把 right 中的元素放在支点元素之后， l e f t 中的元素放在支点元素之前，即可得到最终的结果[ 1 , 2 , 3 , 4 , 5 , 6 , 7 ,8 ]。
把元素序列划分为 l e f t、m i d d l e 和 r i g h t 可以就地进行（见程序 1 4 - 6）。
在程序 1 4 - 6 中，支点总是取位置 1 中的元素。
也可以采用其他选择方式来提高排序性能，本章稍后部分将给出这样一种选择。
程序 14-6 快速排序template<class T> void QuickSort(T*a, int n){// 对 a[0:n-1] 进行快速排序 {// 要求 a[n] 必需有最大关键值 quickSort(a, 0, n-1);template<class T>void quickSort(T a[], int l, int r) {// 排序 a [ l : r ]， a[r+1] 有大值 if (l >= r) return;int i = l, // 从左至右的游标 j= r + 1; // 从右到左的游标 T pivot = a[l];// 把左侧>= pivot 的元素与右侧<= pivot 的元素进行交换while (true) {do {// 在左侧寻找>= pivot 的元素i = i + 1; } while (a < pivot);do {// 在右侧寻找<= pivot 的元素j = j - 1; } while (a[j] > pivot); if (i >= j) break; // 未发现交换对象Swap(a, a[j]);}// 设置 p i v o t a[l] = a[j];贪婪法 a[j] = pivot;quickSort(a, l, j-1); // 对左段排序quickSort(a, j+1, r); // 对右段排序 }它采用逐步构造最优解的思想，在问题求解的每一个阶段，都作出一个在一定标准下看上去最优的决策；决策一旦作出，就不可再更改。
制定决策的依据称为贪婪准则。
贪婪法是一种不追求最优解，只希望得到较为满意解的方法。
贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。
贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。
【问题】背包问题问题描述：有不同价值、不同重量的物品 n 件，求从这 n 件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。
#include<stdio.h>void main(){intm,n,i,j,w[50],p[50],pl[50],b[50],s=0,max;printf("输入背包容量 m,物品种类 n :");scanf("%d %d",&m,&n);for(i=1;i<=n;i=i+1){printf("输入物品的重量 W 和价值P :");scanf("%d %d",&w[i],&p[i]);pl[i]=p[i];s=s+w[i];}if(s<=m){printf("whole choose\n");//return;}for(i=1;i<=n;i=i+1){max=1;for(j=2;j<=n;j=j+1)if(pl[j]/w[j]>pl[max]/w[m ax])max=j;pl[max]=0;b[i]=max;}for(i=1,s=0;s<m && i<=n;i=i+1)s=s+w[b[i]];if(s!=m)w[b[i-1]]=m-w[b[i-1]];for(j=1;j<=i-1;j=j+1)printf("chooseweight %d\n",w[b[j]]);}动态规划的基本思想前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。
