Liny_@NotePad

沉迷ACG中

动态规划求解资源最优分配问题

为第i个工程计算最优时，只需将分配若干给前i-1个工程、剩下的留给当前工程得到的各种分配方案，和只分配给当前工程的方案，取其中的最大值即可；而第一个工程解就是只分配给自身的解。

【算法】与【数据结构】 动态规划 Comments(0) 2009年4月29日 08:12

动态规划求多段图单源最短路径

从终点n-1开始，直到顶点0，对每个点：
遍历其所能达到的各个结点，判断通过该结点访问终点的路径是否小于当前能找到的最短距离，是则更新，否则不变。
  最后，顶点0找到的最短距离必然是该点到达终点n-1的最短距离。
* 局限性：本程序只能求从顶点0到顶点n-1的最短路，且只能从编号较小的点访问编号较大的点。

【算法】与【数据结构】 动态规划 单源最短路径 Comments(0) 2009年4月29日 08:11

贪心法求解单源最短路径问题

虽说之前贴了模版 = = 但还是按照老师的格式写一下……

每次找到距离源点最接近且未被访问的点，对该点能到达的所有结点遍历比较经过该点中转后的距离是否小于之前计算的最短距离，是则更新该结点距离（若之前没访问过还要置其访问标记为真）。最多查找n-1次各遍历过一遍后即可得出最终解。

【算法】与【数据结构】 贪心 dijkstra 单源最短路径 Comments(0) 2009年4月29日 08:08

贪心法：部分背包问题

因可以取物体的部分放入，故每次选择价值重量比最高的物体放入，可保证放入的价值一定最大，满足贪婪选择性质和最有子结构性质，故采用贪心算法求解：
1. 根据各个物体的价值p与重量w计算价值重量比v
2. 根据v降序排序
3. 从当前最大的v的开始，判断该物体重量是否超过背包剩余载重
4. 是则放入背包剩余载重量的物体，加上这部分的价值，跳到7
5. 否则将物体完整放入背包，加上物体的价值
6. 若还有物体未放入背包，则跳到3
7. 输出背包中物体的总价值

【算法】与【数据结构】 贪心 背包问题 Comments(0) 2009年4月29日 08:07

分治法求解二叉树深度

若一个树没有孩子，则它的深度为1；
若一个树只有左孩子，则它的深度就是左孩子的深度+1；
若一个树只有右孩子，则它的深度就是右孩子的深度+1；
若一个树有两个孩子，则它的深度就是两个孩子中较深的那颗深度+1。
由此可以递归得到该树的高度。

【算法】与【数据结构】 分治 Comments(0) 2009年4月29日 08:05

分治法：棋盘覆盖问题

若棋盘规格是1*1，则不用填充；
若棋盘规格大于1*1，则将棋盘分割成四个子棋盘。判断特殊点在哪一个子棋盘中，进入该棋盘继续覆盖，而对其他子棋盘，设置边界点为新特殊点（填充这3个边界点即是填充了一个L型骨牌），并对各个子棋盘继续覆盖。

【算法】与【数据结构】 分治 Comments(0) 2009年4月29日 08:05

分治法：平面最近点对问题

当一个点集中只有两个点时，它们的距离就是最近距离；
当一个点集中有三个点时，它们的距离也可以直接求出；
当一个点集中的点数量大于3时，则将数组拆分成两半，分别计算左右子集的最近距离的平方d（将数量>3的数组一直拆分，最后到只有2个或3个点的点集时即能求解），收集距离中线两侧小于d的点，在这些点中寻找垂直距离小于d的两个点，若存在则说明其为当前能找到的最近点对，更新d为这两点的距离。

【算法】与【数据结构】 分治 Comments(0) 2009年4月29日 08:03

分治法求第K大元素

 k大元素不就是第(n-k+1)小元素么 = =

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. /***************************************
  6. * 选择第k小元素算法
  7. *
  8. * 输入：元素数组A[]，元素个数n，求的k
  9. * 输出：第k小元素
  10. ***************************************/
  11. template<class Type>
  12. Type select(Type A[], int n, int k){
  13.         int i,j,s,t;
  14.         Type m,*p,*q,*r;
  15.         if(n<38){                     //     如果元素个数小于38：则直接排序
  16.                 sort(A,A+n);
  17.                 return A[k-1];
  18.         }
  19.         p = new Type[3*n/4];
  20.         q = new Type[3*n/4];
  21.         r = new Type[3*n/4];
  22.         for( i=0; i<n/5; i++){  //        五个一组，把每组的中值元素存放进数组p
  23.                 mid(A,i,p);
  24.         }
  25.         m = select(p, i, i/2+i%2);      //    递归调用，取得中值元素存入m
  26.         i = j = s = 0;
  27.         for( t=0; t<n; i++){    //  按<m、=m、>m把数组分成三组
  28.                 if(A[t]<m){
  29.                         p[i++] = A[t];
  30.                 }else{
  31.                         if(A[t]==m){
  32.                                 q[j++] = A[t];
  33.                         }else{
  34.                                 r[s++] = A[t];
  35.                         }
  36.  
  37.                 }
  38.         }
  39.         if(i>k){                                //      若k<i，则该元素就在数组p中，进入p继续查找
  40.                 return select(p,i,k);
  41.         }else{
  42.                 if(i+j>=k){               //   若i<k<i+j，则该元素在q数组中，即值为m
  43.                         return m;
  44.                 }else{        //        若k>i+j，则该元素在r数组中，进入r继续寻找
  45.                         return select(r,s,k-i-j);
  46.                 }
  47.         }
  48. }
  49.  
  50. /***************************************
  51. * 计算中值元素
  52. *
  53. * 输入：元素数组A[]，组号i
  54. * 输出：存放中值元素的数组p[]
  55. ***************************************/
  56. template<class Type>
  57. void mid(Type A[], int i, Type p[]){
  58.         int k = 5*i;
  59.         if(A[k]>A[k+2]){
  60.                 swap(A[k], A[k+2]);
  61.         }
  62.         if(A[k+1]>A[k+3]){
  63.                 swap(A[k+1], A[k+3]);
  64.         }
  65.         if(A[k]>A[k+1]){
  66.                 swap(A[k],A[k+1]);
  67.         }
  68.         if(A[k+2]>A[k+3]){
  69.                 swap(A[k+2],A[k+3]);
  70.         }
  71.         if(A[k+1]>A[k+2]){
  72.                 swap(A[k+1],A[k+2]);
  73.         }
  74.         if(A[k+4]>A[k+2]){
  75.                 p[i] = A[k+2];
  76.         }else{
  77.                 if(A[k+4]>A[k+1]){
  78.                         p[i] = A[k+4];
  79.                 }else{
  80.                         p[i] = A[k+1];
  81.                 }
  82.         }
  83. }
  84.  
  85. int main(){
  86.         int n,m;
  87.  
  88.         cout<<"请输入数组元素个数：";
  89.         cin>>n;
  90.        
  91.         cout<<"请输入要求的k：";
  92.         cin>>m;
  93.        
  94.         int *A = new int[n];
  95.         int i;
  96.  
  97.         cout<<"请输入数组元素："<<endl;
  98.         for(i=0;i<n;i++){
  99.                 cin>>A[i];
  100.         }
  101.        
  102.         cout<<"第"<<m<<"大元素是：";
  103.         cout<<select(A,n,n-m+1)<<endl;    // 输出第(n-m+1)小元素<=>第m大元素
  104.  
  105.         return 0;
  106. }

【算法】与【数据结构】 分治 Comments(0) 2009年4月29日 08:02