m[1][c]=m[2][c]; if(c>=w[1])
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); }
（3）回溯法 O(2n)
cw:当前重量 cp:当前价值 bestp：当前最优值 voidbacktrack(inti) 包问题的贪心算法
void Knapsack(int n,float M,float v[],float w[],float x[]) {
Sort(n,v,w); int i;
for (i=1;i<=n;i++) x[i]=0; float c=M;
for (i=1;i<=n;i++) { if (w[i]>c) break; x[i]=1; c - =w[i]; }
if (i<=n) x[i]=c/w[i]; }
2.最大子段和: 动态规划算法 int MaxSum(int n, int a[]) {
int sum=0, b=0； 速排序 template
void QuickSort (Type a[], int p, int r) {
if (p int q=Partition(a,p,r); QuickSort (a,p,q-1); 列问题 Template void perm(Type list[], int k, int m ) { 定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。 据此容易设计出二分搜索算法： template int BinarySearch(Type a[], const Type& x, int l, int r) { while (l<=r ){ int m = ((l+r)/2); if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; } return -1; } 6、合并排序描述如下： template void Mergesort(Type a[ ], int left, int right) { if (left int i=( left+right)/2; Mergesort(a, left, i ); Mergesort(a, i+1, right); Merge(a,b, left,i,right);计算机求解问题的步骤： 1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制 2. 算法定义： 算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3.算法的三要素 1、操作2、控制结构3、数据结构 13. 分治法与动态规划法的相同点是： 将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原 问题的解。 两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。 回溯法中常见的两类典型的解空间树是子集树和排列树。 22.请叙述动态规划算法与贪心算法的异同。 共同点：都需要最优子结构性质，都用来求有优化问题。 不同点： 动态规划：每一步作一个选择—依赖于子问题的解。 贪心方法：每一步作一个选择—不依赖于子问题的解。 动态规划方法的条件：子问题的重叠性质。 可用贪心方法的条件：最优子结构性质；贪心选择性质。 动态规划：自底向上求解；贪心方法： 自顶向下求解。可用贪心法时，动态规划方法可能不适用；可用动态规划方法时，贪心法可能不适用。 23. 请说明动态规划方法为什么需要最优子结构性质。 答：最优子结构性质是指大问题的最优解包含子问题的最优解。 动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构. 24. 请说明： (1)优先队列可用什么数据结构实现 (2)优先队列插入算法基本思想 (3)优先队列插入算法时间复杂度 答：（1）堆。 （2）在小根堆中，将元素x插入到堆的末尾， 然后将元素x的关键字与其双亲的关键字比较， 若元素x的关键字小于其双亲的关键字， 则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键字大于双亲的关键字，或元素x到根为止。 （3）O( log n) 26. 在算法复杂性分析中，O、Ω、Θ这三个记号的意义是什么在忽略常数因子的情况 下，O、Ω、Θ分别提供了算法运行时间的什么界 答： 如果存在两个正常数c和N0,对于所有的N≥N0，有|f(N)|≤C|g(N)|，则记作：f(N)= O(g(N))。这时我们说f(N)的阶不高于g(N)的阶。 若存在两个正常数C和自然数N0，使得当N ≥ N0时有|f(N)|≥C|g(N)|，记为 f(N)=(g(N))。这时我们说f(N)的阶不低于g(N)的阶。 如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g(N)| ≤|f(N)| ≤ c2|g(N)| 则记作 f(N)= (g,(N) O、Ω、Θ分别提供了算法运行时间的上界、下界、平均 五、算法设计与分析题 1．用动态规划策略求解最长公共子序列问题： （1）给出计算最优值的递归方程。 （2）给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公 共子序列，要求给出过程。 答：1 (2) Ｙ Ａ Ｂ Ｃ Ｂ Ｘ 0 0 0 0 Ｂ 0 0 1 1 1 Ｃ 0 0 1 2 2 Ｄ 0 0 1 2 2 Ａ 0 1 1 2 2 最长公共子序列：｛ＢＣ｝ 2．对下列各组函数f (n) 和g (n)，确定f (n) = O (g (n)) 或f (n) =Ω(g (n))或 f(n) =θ(g(n))，并简要说明理由。 (1) f(n)=2； g(n)=n! (2) f(n)=n； g (n)=log n2 (3) f(n)=100； g(n)=log100 (4) f(n)=n3； g(n)= 3n (5) f(n)=3n； g(n)=2n 答： n ?
相关推荐：
loading