1、有0-1背包问题如下：
n=3，c=30，p=[45，25，25]，w=[16，15，15]。
用队列式、优先队列式分支限界法求最优解。（画解空间树并详细描述求解过程）
解：队列式分支限界法：
a] b, c =>b, c
b, c] d, e =>e
c, e] f, g =>f, g
e, f, g] j, k =>k(45) [1,0,0]
f, g] l, m =>l(50) [0, 1, 1] m(25)
g] n, 0 =>n(25), o(0)
不搜索以不可行结点为根的子树。
优先队列式分支限界法：
a] b, c =>b(45), c(0)
b, c] d, e =>e(45)
e, c] j, k =>k(45) [1, 0, 0]
c] f, g =>f(25), g(0)
f, g] l, m =>l(50), 0, 1, 1] m(25)
g] n, o =>n(25), o(0)
可用剪枝函数加速搜索。
2、用队列式、优先队列式分支限界法求解如下图的四城市旅行商问题。（画解空间树并详细描述求解过程）
3、有0-1背包问题如下：
n=6，c=20，p=（11，8，15，18，12，6），w=（5，3，2，10，4，2）。
试分别画出用回溯法求解时的搜索情况。
4、用递归回溯算法求解四后问题。（写出c++算法描述的关键**、画出求得第一解时的搜索树）
5、用递归回溯算法求解图的m着色问题。（写出c++算法描述的关键**）
1、 贪心算法的基本要素？动态规划算法的基本要素？贪心算法的基本要素：贪心选择性质和最优子结构性质。动态规划的基本要素：最优子结构性质和子问题重叠性质。
2、 比较动态规划法、分治法和贪心法之间的异同。
动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的 (即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。
动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。
3、 贪心算法与动态规划算法的差异？
4、 分支限界法的基本思想及其分类？ 队列式分支限界法、优先队列式分支限界法。
5、 什么是最优子结构性质？某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。
6、 解释记号o（上界）、（下界）、（同阶）和（低阶）的意义。
5、分支限界法与回溯法的区别？191页。
6、动态规划算法的基本思想与基本要素？48页。
7、什么是算法， 算法具有的特性是什么？算法是指解决问题的一种方法或一个过程。性质：输入、输出、确定性、有限性。
8、制定一个算法一般要经历哪几个阶段？制定算法一般要经过设计、确认、分析、编码、检查、调试、计时等阶段。
9、什么是最优解？使目标函数取得极值（最大或最小）的解称为最优解。
程序填空题。
1、回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。
void backtrack (int t)
if (t>n) _output(x)_;
elsefor (int i=f(n,t);i<=g(n,t);i++)
else if (c[i-1][j]>=c[i][j-1])
else
构造最长公共子序列。
void lcs(int i，int j，char *x，int **b)
if (i ==0 ||j==0) return;
if (_b[i][j]==1_)
return -1;//未找到x
4、递归算法求全排列问题。
void perm(int list,int k,int m)
elsefor(int i=k;i<=m;i++)
int t=list[k];list[k]=list[i];list[i]=t; /和首元素交换。
perm(list,k+1,m)__产生list[k+1:m]的所有排列。
t=list[k];list[k]=list[i];list[i]=t取消前面的交换。
5、递归算法求汉诺塔问题。
void move(char x, char y)
//将第n个圆盘从塔座x移到塔座y的顶部。
cout < << x < void hanoi(int n, char x, char y, char z) //将x上部的n个圆盘移到y上，顺序不变。 if (n>0) 6、快速排序。 void quicksort (type a,int p, int r) if (p int q=partition(a,p,r);/分划操作。 quicksort (a,p,q-1); 对左半段排序。 quicksort (a,q+1,r); 对右半段排序。 int partition (type a,int p, int r) int i = p, j = r + 1; type x=a[p]; 将< x的元素交换到左边区域。 将》 x的元素交换到右边区域。 while (true) m[1][c]=m[2][c]; 第一行不计算，减少计算量。 if(c>=w[1]) m[1][c]=max(_m[1][c]_ m[2][c-w[1]]+v[1]_) 1.计算题。2.使用分治算法找一组数的最大最小数。采用如下设计思想 1 将数据集 s 均分为 s1 和 s2 2 求解 s1 和 s2 中的最大和最小值 3 最终的最大和最小值可以计算得到 min s1,s2 max s1,s2 4 采用同样的处理方法递归处理 s1 和 s2。函数 a n，m 有 ... 一 查找二叉树。1 什么是二分查找树？它是二叉树，具有左子树中的每个节点值都小于根节点值，右子树中的每个节点值都大于根节点值的性质。2 如何查找？1 将该值与根结点进行比较，2 若相等，则查找成功，结束查找 3 若小于，则对左子树进行查找操作，回到步骤 1 4 若大于，则对右子树进行查找操作，回到步... 一 算法的定义 对一类问题的机械的 统一的求解方法称为算法。二 算法的特点 有限性 确定性。注 一般来说，算法有一个或多个输出。三 算法的描述方式 自然语言 流程图 程序设计语言 伪 四 自然语言描述中的典型例题 高斯消元法解线性方程组，即先将方程组化为一个三角形方程组，再通过回代过程求出方程组的解...算法复习整理
算法设计复习
算法初步复习