因为准备有关于算法分析与设计的考试，所以对一些经典的算法问题做了总结。
一、分治策略
分（Divide）
将规模为n的问题分解为 k 个规模较小的子问题
治（Conquer）
对k个子问题分别求解，然后将各个子问题的解合并得到原问题的解
分治策略是从下至上求解并将合并得到解
/*二分查找法分治策略*/
Begin
输入有序数组a[],查找元素x,数组最左边下标i，最右边下标j
i->0,j->a.length
1.while(i>=j)循环执行:
1.1 设置 m =(i+j)/2;
1.2 if(x==a[m]) return m;
1.3 if(x<a[m]) j=m-1; else i=m+1;
2.return -1;
End
二、动态规划
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，并且它能够解决子问题不相互独立时的某些情况
不同子问题的数目常常只有多项式量级，即在用分治法求解时，有些子问题被重复计算了有限多次。
- 基本要素
最优子结构
问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质
重叠子问题
递归求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质 - 基本步骤
找出最优解的性质，并刻划其结构特征
递归地定义最优值
以自底向上的方式计算出最优值
根据计算最优值时得到的信息，构造最优解
/*0-1背包问题*/
int knapSack(int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;
if (wt[n-1] > W)
return knapSack(W, wt, val, n-1);
else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
knapSack(W, wt, val, n-1)
);
}
三、贪心算法
顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的近似值。
贪心算法需考虑到的方面
1）候选集（C）问题可能解的集合
2）解集（S）满足问题的完整解，S是C的一个子集
3）可行解函数用于检验S是否构成问题的一个可行解
4）选择函数即贪心策略，也是贪心算法的关键
5）约束函数检测解集S加入一个候选对象是否满足约束
/*dijkstra算法单源最短路径*/
Begin
1 初始 s={1},v={2...n},dist[i]=c[i][j];
2
2.1 u=min{dist[i][j]|i属于v}
2.2 s=sU{v},v=v-{u};
2.3 对于 v 中顶点 i
if(dist[u]+c[u][i]<dist[i][j]) dist[i]=dist[u]+c[u][j]
3.输出dist
End
四、回溯法
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索
- 基本思想
1）针对所给问题，定义问题的解空间
2）确定易于搜索的解空间结构
3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
剪枝函数（Pruning Function）：约束条件或目标函数的界，即判定该节点是否包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的搜索，这便是所谓的剪枝
/*0-1背包问题回溯算法*/
Begin
设Backtrakc(i)表示对第i层结点的搜索
1. if(i>n)则返回当前解bestp,结束算法
2. if 当前背包重量 cw+w[i]<c,进入左子树
2.1 cw+=w[i];当前价值cp+=v[i];
2.2 搜索下一层结点 Backtrack(i+1);
2.3 回退,cw-=w[i],cp=v[i]];
3. 如果Bound(i+1)>bestp,进入右子树,即Backtrack(i+1)
End
五、分支界限法
求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解
搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树
- 基本思想
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止
/*任务分配问题分支界限法*/
Begin
1 根据限界函数计算目标函数的下界down;采用贪心法得到上界up;
2. 将待处理结点活结点表初始化为空；
3. for(i=l;i<=n;i++)
x[i]= 0;
4. k=l;i=0; //为第k个人分配任务，i为第k-1个人分配的任务
5. while (k>=l)
5.1 x[k]=l;
5.2 while (x[k]<=n)
5.2.1 如果人员k分配任务x[k]不发生冲突，则
5.2.1.1 计算目标函数值lb;
5.2.1.2 若lb<=up,则将i，<x[k]，k>lb存储在活结点表中;
5.2.2 x[k]=x[k]+l;
5.3 如果k==n且叶子结点的lb值在活结点表中最小,
则输出该叶子结点对应的最优解;
5.4 否则，如果k==n且活结点表中的叶子结点的lb值不是最小,则
5.4.1 up=活结点表中的叶子结点最小的lb值；
5.4.2 将活结点表中超出目标函数界的结点删除；
5.5 i=活结点表中lb最小的结点的x丨k]值；
5.6 k=活结点表中lb最小的结点的k值;k++;
End
