概述
一.感想：
在大一下学期的算法基础学习中，毫无疑问，自己的代码水平以及思维深度都有了显著的提高。虽然刚开始做题的时候会感觉到有些无从下手，有时甚至一道题那过来，就会感到头脑毫无思路，这是很正常的一件事，但是记住一件事：不要回避，回避只会令自己更加懒惰，当你全身心的投入到算法知识的海洋中去的，你会感叹原来“哦，原来三分算法可以用到现实当中无人驾驶汽车拐弯技术中去啊”，“原来最小生成树可以跟某些查询系统结合求最短路径啊”，“嗯，路径压缩能使并查集的操作大大简化”，你会发现acm就像一场游戏一样，做出一道题来后还是很有成就感的。另外，我觉得要注意的一件事就是要注意总结和培养自己独立思考.勇于尝试的能力。1.所谓的独立思考，就是不要养成做不来就上网搜别人代码的习惯，如果实在做不出来，可以尝试问一下别人思路，然后再尝试自己去实现，等做出来之后再看别人的代码，学习一些好的地方。2.而所谓的敢于尝试，就是不要怕错，编程是一件很特别的事情，他可以在当场验证你的理论的正确性，当你头脑清晰时，你就是国王。所以，不要把错藏在心里，打开电脑自己试下，自然就明了了，也只有这样，你才能从自己完成的每一道题中获得快乐。3.最后就是解题总结了，在这个过程中，你会重新梳理一遍代码过程，做好注释，你会更有收获，不至于几个月后忘得一干二净。
二.学习历程：
首先列一个清单，看看自己到底学会了多少东西，在这一个学期的学习中。简单的贪心算法，贪心与其说是一种算法，倒不如说是一种思想，在寻求最优解的过程中，都在寻求局部的最优解，解这类贪心问题策略关键是分析局部的最优解是否能构造出问题的最终解。简单的动态规划问题：这类题的关键就是就是寻找问题状态转移方程，有时候实在想不出就可以用待定系数法来求出状态转移方程。背包问题。提前学到了数据结构的内容：STL中先进先出的栈，先进后出的队列，优先队列，map容器等，以及一些函数size. Empty.pop. Push的操作。Sort函数的使用，调用sort排序。打表这种方法。搜索专题：学会了深度优先搜索DFS，广度优先搜索BFS这两种搜索的基本思想和过程分析。学到了记忆化搜索这种以空间换时间的优化策略，二分查找，三分查找。图算法：目前仅学会了几种方法，并查集的操作解决点集的所需连通数，用Prim算法和kruskal 算法（求边上的权值，额，好像没啥区别）解决最小生成树问题，bellman-ford，spfa，dijkstra来解决单源最短路径问题，松弛技术等。下面详细描述各模块的内容。。
贪心算法：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解
贪心算法一般用于以下几种问题：
转化为背包划分，活动时间的安排，数字组合问题但是该算法也存在一些问题：不能保证求得的最后解释最佳的；不能用来求最大或着最小解的问题；只能求满足某些约束条件的可行解的范围。
例如：第一题就是一种活动安排问题，活动安排问题要注意的一个点就是弄清楚题目是串行的还是并行的，找出标准。
模板：
按活动的结束时间升序排序
排序比较因子：
bool cmp(const action &a, const action &b)
{
if (a.f<=b.f) return true;
return false;
}
使用标准模板库函数排序（下标0未用）：
sort(a, a+n+1, cmp);
形参数组b用来记录被选中的活动
void GreedySelector(int n, action a[], bool b[])
{
b[1] = true; //第1个活动是必选的
//记录最近一次加入到集合b中的活动
int preEnd = 1;
for(int i=2; i<=n; i++)
if (a[i].s>=a[preEnd].f)
{
b[i] = true;
preEnd = i;
}
}
背包问题：这类题一般分为以性价比或者是用物品的重量的标准衡量。
模板：
struct bag{
int w; //物品的重量
int v; //物品的价值
double c; //性价比
}a[1001]; //存放物品的数组
排序因子（按性价比降序）：
bool cmp(bag a, bag b){
return a.c >= b.c;
}
使用标准模板库函数排序（最好使用stable_sort()函数，在性价比相同时保持输入的顺序）：
sort(a, a+n, cmp);
//形参n是物品的数量，c是背包的容量M，数组a是按物品的性价比降序排序
double knapsack(int n, bag a[], double c)
{
double cleft = c; //背包的剩余容量
int i = 0;
double b = 0; //获得的价值
//当背包还能完全装入物品i
while(i<n && a[i].w<cleft)
{
cleft -= a[i].w;
b += a[i].v;
i++;
}
//装满背包的剩余空间
if (i<n) b += 1.0*a[i].v*cleft/a[i].w;
return b;
}
贪心算法一般在开始策略前会进行排序，排序后再进行最优化选择。排序一般直接使用sort函数，在学这门课之前，我写排序还是用最基本版的冒泡算法或者简单选择。而又学了数据结构，排序的方法就很多了，直接用sort函数就行啦。还有一种很好用的容器是优先队列（一个拥有权值观念的queue，自动依照元素的权值排列，权值最高排在前面），这个直接放进数去就可以自动排序，更好用。
图的应用中最小生成树的算法都是很好的贪心算法。事实上贪心算法可以和其他很多算法结合起来，更好用，结果也更准确。
搜索专题：
1 二分算法：
在一个单调有序的集合中查找元素，每次将集合分为左右两部分，判断解在哪个部分中并调整集合上下界，重复直到找到目标解。它主要应用于单调函数给定一个因变量，求解自变量问题，取中点函数值num[mid]与X比较。
模板代码：int mid，LOW,high;
//x：待查找的元素， n：数组集合大小， num数组单调递增（或递减）
int low=0,high=n,mid; //low:集合下界 high：集合上节
while(low<=high)
{
mid=(low+high)/2; //mid:将集合分割为两部分
if(num[mid]==x) //查找到符合元素x
{
return mid;
break;
}
else if(num[mid]<x) //x在右边部分，调整集合下界
low=mid;
else //x在左边部分，调整集合上界
high=mid;
}
2 三分算法：
当需要求某凸性或凹形函数的极值，通过函数本身表达式并不容易求解时，就可以用三分法不断逼近求解、
先取mid=L+R，mmid=mid+R，再通过F（mid）与F(mmid)谁离函数机智点近进行比较，不断逼近极值点、
代码模板：
double mid, midmid;//cal（）函数假设先增后减double mid, midmid;
while ( low + eps < high )
{
mid = (low + high) / 2;
midmid = (mid + high ) / 2;
double cmid = cal(mid);
double cmidmid = cal(midmid);
if ( cmid > cmidmid )
high = midmid;
else
low = mid;
}
深度优先算法：(通过遍历子状态路径来寻求最优解，本质就是递归)
2. 依次从v的未被访问的邻接点出发，对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止、
用队列实现，生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。基本思想：从初始状态S 开始，利用规则，生成所有可能的状态。构成的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。
技巧：
通过做这几道题来看，有的题目完全就是可以通过dp，递归等别的方法来解决，动态规划的优点是用一个数组来储存 状态值，用空间换取了时间（记忆化搜索）。这类题目难点就在于想到用这个方法还有思考出状态转移方程的过程，假如说如果实在想不出状态转移方程就比如说那个（折线划分区域的题目）不好想，就可以采用待定系数法，
f(x)=a*x^2+b*x+c,,f(x)=a*x^3+b*x^2+c*x+d代数来解决。
这里要记住几类题目：1 求最大字段长的和（ 可以扩展到两段乃至M段的子段长的问题）前者枚举两个字段的起始点i j ，后者：其中dp[i][j]是ij为起始点的子段，最后求DP[M][N]即可。
dp[i][j] = max{dp[i][j-1],0}+a[j] (i = 1,i <= j <= N)
dp[i][j] = max{dp[i-1][j-1],dp[i][j-1]}+a[j] (2 <= i <= M , i <= j <= N)
2 子矩阵的和 先枚举再压缩成一维的字段处理
3 公式题型
背包问题：
背包基础，分为01背包，完全背包，多重背包，区间背包，没什么好说的，就是套公式。
上模板：
01背包
for i=1..N
for v=v..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
完全背包
for i=1..N
for v=0..v
f[v]=max{f[v],f[v-c[i]]+w[i]};
多重背包：
<pre name="code" class="cpp">void zeroonepack(int cost,int wei)
{
int i;
for(i=v;i>=cost;i--)
{
dp[i]=max(dp[i],dp[i-cost]+wei);
}
}
void complete(int cost,int wei)
{
int i;
for(i=cost;i<=v;i++)
{
dp[i]=max(dp[i],dp[i-cost]+wei);
}
}
void mutiplepack(int cost,int wei,int cnt)
{
if(cost*cnt>=v)
{
complete(cost,wei);
return;
}
else
{
int p=1;
while(p<cnt)
{
zeroonepack(p*cost,p*wei);
cnt=cnt-p;
p=2*p;
}
zeroonepack(cnt*cost,cnt*wei);
}
}图论 ：在这个专题中，我了解到邻接矩阵.邻接表的图的存储结构。了解了一些连通图.有向图.无向图的基本概念。会用SPFA算法解决单源最短路径问题（嗷嗷，一招鲜吃遍天
），会用Prim与Kruskal解决最小生成树问题。
1.并查集：
并查集的基本思想:
初始化
for i:=1 to n do father[i]:=i;
因为每个元素属于单独的一个集合，所以每个元素以自己作为根结点。
2.查找（路径压缩）
寻找根结点编号并压缩路径：
begin
if father[v]=v then exit(v);
father[v]:=find(father[v]);
return father[v];
end;
3.合并(合并时最好把深度小的树合并到深度深的树中去)启发式合并
begin
x:=find(x);
y:=find(y);
if(x!=y)
father[x]=y;
end;
1）Prim算法：
基本思想：
任取一个顶点加入生成树；
在那些一个端点在生成树里，另一个端点不在生成树里的边中，取权最小的边，将它和另一个端点加进生成树。
重复上一步骤，直到所有的顶点都进入了生成树为止。
Prim算法一般适用于稠密图。因为prim算法是针对于结点的算法，边的多少与算法的代价关系不太大。
（2）kruskal算法
kruskal算法的基本思想：
对所有边从小到大排序；
依次试探将边和它的端点加入生成树，如果加入此边后不产生圈，则将边和它的端点加入生成树；否则，将它删去；
直到生成树中有了n-1条边，即告终止。
将边按权值从小到大排序后逐个判断，如果当前的边加入以后不会产生环，那么就把当前边作为生成树的一条边。
最终得到的结果就是最小生成树，一般和并查集一块使用。
Kruskal算法一般用于稀疏图，kruskal是针对于边的算法，所以边越少越好。
并查集和最小生成树一般是用于将图连通，求最小代价了或者求最少需要修几条路。这一部分就在那一直修路。
SPFA算法：
SPFA 其实就是Bellman-Ford的一种队列实现，减少了冗余，即松驰的边至少不会以一个d为∞的点为起点。
算法：
1.队列Q={s}
2.取出队头u,枚举所有的u的临边 .若d(v)>d(u)+w(u,v)则改进 ，pre(v)=u，由于d(v)减少了，v可能在以后改进其他的点，所以若v不在Q中，则将v入队。
3.一直迭代2，直到队列Q为空(正常结束)，或有的点的入队次数>=n（含有负圈）。
尽管这仅仅是图论的一小部分，但我感觉这还是不好理解的，应该是最难的一部分，但在生活中会有很广泛的应用，（确定最短行车路线，GPS的路径规划，某滴，地图软件）还是会很有用的。
体会：半年前匆匆开始，相信天道酬勤，相信未来的自己一定不会忘记在漆黑的夜晚曾经流过的汗水，韶华易逝，不负自己。
最后
以上就是害怕银耳汤为你收集整理的ACM总结体会的全部内容，希望文章能够帮你解决ACM总结体会所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复