锐客网

  1. 首页 > it技术 > >

C++|贪心，深度优先(9)

一、贪心算法 1.1 简介 贪心本质：一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部优先选择从而得到全局最优解决方案。
就如《算法导论》里所说的：“人要活在当下” “看清楚眼前”……贪心算法正是“活在当下，看清楚眼前”的办法。从问题的初始解开始，一步一歩地做出当前最好的选择，逐步逼近问题的目标，尽可能地得到最优解，即使达不到最优解，也可以得到最优解的近似解。
贪心算法在解决问题的策略上“目光短浅”，只根据当前已有的信息就做出选择， 一旦做出了选择，不管有什么样的结果，这个选择都不会改变。因此，贪心算法在实际中得到大量的应用。在贪心算法中，我们需要注意以下几个问题。

（1）没有后悔药。一旦做出选择，不可以反悔。
（2）有可能得到的不是最优解，而是最优解的近似解。
（3）选择什么样的贪心策略，直接决定算法的好坏。
有木有觉得贪心算法有点像 冒泡排序？
其实，这不是 贪心算法像冒泡排序 ，而是冒泡排序使用了贪心算法，它的贪心策略就是每一次从剩下的序列中选一个最大的数，把这些选出来的数放 在一起，就得到了从大到小的排序结果，如图所示：
C++|贪心，深度优先(9)
文章图片

1.2 例题&代码 例1
在N行M列的正整数矩阵中，要求从每行中选出一个数，使得选出的N个数的和最大。
例2
在一个N*M的方格阵中，每一格子赋予一个数（即权值），规定每次移动时只能向上或向右。现找出一条路径，使其从左下角至右上角所经过的权值之和最大
分析1
本题可以用贪心算法求解。选N次，每次选出相应行中的最大值即可。
分析2
我们以2*3的矩阵为例：
346 1210

若按贪心算法求解：所得路径为1->3->4->6
若按动态规划求解，所得路径为1->2->10->6
所以这里贪心算法求解，得到的并不是问题的最优解，而是近似解
例题1
人民币找零 在50元和100元面值的人民币出现之前，人民币仅由10元、5元、2元、1元、5角、2角、1角和5分、2分、1分面值的钱币组成。现给定一个10000元以内，精确到1分的人民币数值，请你用最少的钱币张数，找出相应的钱数。
样例输入
【C++|贪心，深度优先(9)】17.32
样例输出
6
分析
给定钱币数为17元3角2分，则输入数据为17.32，则相应的输出为6（钱币总张数，此数应最小）
10 1 (以下为各种面值钱币的张数，不需要使用的钱币不必列出)
5 1
2 1
0.2 1
0.1 1
0.02 1
例题2
均分纸牌 有 n 堆纸牌，编号分别为 1，2，…, n。每堆上有若干张，但纸牌总数必为 n 的倍数可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 n 的堆上取的纸牌，只能移到编号为 n-1 的堆上；其他堆上取纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆纸牌数都一样多。
输入格式
n（n 堆纸牌，1 <= n <= 100）
输出格式
所有堆均达到相等时的最少移动次数。
样例输入
4
样例输出
9 8 17 6
不给分析
代码
#include using namespace std; int n,ave=0,step=0,a[100]; int main() { cin>>n; for(int i=1; i<=n; i++) { cin>>a[i]; ave+=a[i]; } ave/=n; for(int i=1; i<=n; i++) a[i]-=ave; int i=1; for(; i=n) break; a[i+1]+=a[i]; a[i]=0; } cout<<

例题3
删数问题 键盘输入一个高精度的正整数n(≤240位)，去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。
输入格式
n 代表一个高精度正整数
s 去掉数字的个数
输出格式
最后剩下的最小数
样例输入
178543
4
样例输出
13
分析
由于正整数n的数位为240位，所以很自然地采用字符串类型存贮n。
是不是删除最大的那s个数字呢？ 当然不是，大家很容易举出一些反例。比如：178593
代码
#include using namespace std; string n; int s; int main() { cin>>n>>s; while(s>0) { int i=0; while(i

选择区间不相交问题
给定n个开区间(ai,bi)，选择尽量多个区间，使得这些区间两两没有公共点。
策略：首先，按照结束时间b1<=b2<=….<=bn的顺序排序，依次考虑各个活动 ，如果没有和已经选择的活动冲突就选；否则，就不选。
【正确性】
假设bj
例题4
活动安排 设有n个活动集合E={1,2,3……n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 i 都有一个使用该资源的起始时间si和一个结束时间fi，且si
输入格式
第一行一个整数n（n<=1000）; 接下来的n行，每行两个整数s i和f i
输出格式
输出尽可能多的互相兼容的活动个数。
样例输入
4
1 3
4 6
2 5
1 7
样例输出
2
代码
#include using namespace std; struct node { int st,ed; }a[1005]; bool cmp(node x,node y) { return x.ed>n; for(int i=1; i<=n; i++) cin>>a[i].st>>a[i].ed; sort(a+1,a+n+1,cmp); int t=a[1].ed; int ans=1; for(int i=2; i<=n; i++) if(a[i].st>=t) { ans++; t=a[i].ed; } cout<

二、深度优先搜索 2.1 简介 搜索是什么？
1.复杂问题的直观想法
2.非常朴素的写题思路
3.暴力骗分的不二法宝
4.按照问题决策发展顺序，遍历问题所有状态空间的求解方法
搜索的类型
1.枚举
2.递归
3.回溯
4.深度优先
5.广度优先
6.记忆化
搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。
回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。
在我们平常的 NOIP (CSP-J/S) 赛中，如果我们真有不会做的题时，我们就可以用搜索来做；**做不到AC (Accepted) ，就把暴力分得到。
2.2 例题 例
跳马问题： 有一只中国象棋中的“马”，在半张棋盘的左下角出发，向右上角跳去。规定只许向右跳（可上，可下，但不允许向左跳），如下图就是一种跳法。请编程求从起点A到终点B共有多少种不同跳法。
2.3 知识点 深度优先搜索算法是搜索中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优先的顺序扩展所有可能情况，当所有可能情况都探索过且都无法到达目标的时候，再回退到上一个出发点，继续探索另一个可能情况，这种“不撞南墙不回头”寻找目标的方法也称为“回溯法”，所以，深度优先搜索也是一种“盲目”搜索。
2.4 例题&代码
拯救瑞恩 有一天，大兵瑞恩在穿越亚马逊丛林时迷路了，他的好友凯西得知后准备去拯救瑞恩,凯西搞到了亚马逊丛林的地图，决定快速去拯救瑞恩……


亚马逊丛林由n行m列的单元格组成（n和m都小于等于50），每个单元格要么是空地，要么是大树，你的任务是帮助凯西找到一条从起点到瑞恩所在位置的最短路径，注意大树是不能通过的，当然凯西也不能走到丛林外边。


首先，我们可以用一个二维数组来存储这个丛林，刚开始的时候，凯西处于丛林的入口处（1,1），瑞恩在（p,q）。其实，就是找一条从（1,1）到（p,q）的最短路径。如果你是凯西，你该怎么办呢？凯西最开始在（1,1），他只能往右走或者往下走，但是凯西究竟是该往下走还是往右走呢？他只能一个一个地去尝试。我们可以先让凯西往右走，直到走不通的时候再回到这里，再去尝试另外一个方向。我们这里规定一个顺序，按照顺时针方向来尝试（即按照右、下、左、上的顺序去尝试）。


我们先来看看凯西一步之内可以到达的点有哪些？只有（1,2）和（2,1）。根据刚才的策略，我们先往右边走，凯西来到了（1,2）这个点，来到（1,2）这个点之后凯西又能到达哪些新的点呢？只有（2,2）这个点，因为（1,3）这个大树是无法到达的，（1,1）是刚才来的路径已经走过的点，也不能走，所以只能到（2,2）这个点，但是瑞恩并不在这个点上，所以凯西还得继续往下走，直至无路可走或者找到瑞恩为止。请注意，此处不是一找到瑞恩就结束了，因为刚才只尝试了一条路，而这条路并不一定是最短的。刚才很多地方在选择方向的时候都有多种选择，因此我们需要返回到这些地方继续尝试往别的方向走，直到把所有可能都尝试一遍，最后输出最短的一条路径。
图片在我上传的文件里 代码
#include using namespace std; int n,m,p,q,min=99999999; Int a[51][51],book[51][51]; void dfs(int x,int y,int step) { int next[4][2]={{0,1},//向右走 {1,0}, //向下走 {0,-1}, //向左走 {-1,0}} //向上走 int tx,ty,k; if(x==p&&y==q) { if(stepn||ty<1||ty>m) continue; if(a[tx][ty]==0&&book[tx][ty]==0) { book[tx][ty]=1; //标记这个点已经走过 dfs(tx,ty,step+1); //开始尝试下一个点 book[tx][ty]=0; 尝试结束，取消这个点的标记 } } return; } Int main() { int I,j,startx,starty; cin>>n>>m; for(i=1; i<=n; i++) for(j=1; j<=m; j++) cin>>a[i][j]; cin>>startx>>starty>>p>>q; book[startx][starty]=1; dfs(startx,starty,0); cout<

2.5 深度优先搜索的算法框架 深度优先搜索（Depth First Search，DFS），简称深搜，其状态“退回一步”的顺序符合“后进先出”的特点，所以采用“栈”存储状态。深搜适用于要求所有解方案的题目。
框架
void dfs(int dep, 参数表 ) { 自定义参数 ; if( 当前是目标状态 ) { 输出解或者作计数、评价处理 ; } else for(i = 1; i <= 状态的拓展可能数 ; i++) if( 第 i 种状态拓展可行 ) { 维护自定义参数 ; dfs(dep+1, 参数表 ); } }

*更多例题可以在我上传的资源中找到
THE END 好了，今天就说到这儿吧（毕竟后面的我还没有学呢~）
这是我第3次写博客自我感觉良好。
*题目均来自JZOJ网站（39.98.198.136），照片均来自老师PPT，部分文字来自老师PPT

    推荐阅读


    上一篇：数据结构|数据结构基础，STL(8)

    下一篇：问题记录-当glibc detected *** free(): invalid next size (normal)出现