4-简单算法.ppt

1、ACM/ICPC程序设计,简单算法,模拟算法及题目 枚举算法及题目 贪心算法及题目 综合实例,一个简单的模拟题,题目（zju1708：Robot Motion） 以矩阵形式给定一张地图和机器人的初始位置。矩阵上每一点的字母代表在这一点机器人的移动方向。如果机器人按图中信息能走出的话输出需要的步数。如果机器人进入某个循环则输出循环前所走的步数和循环的长度。,Sample input and output：,Sample Input 3 6 5NEESWEWWWESSSNWWWW4 5 1SESWEEESNWNWEENEWSEN0 0 0,Sample Output 10 step(s) to e

2、xit3 step(s) before a loop of 8 step(s),问题分析,我们有什么信息？ 地图，起点 我们要什么？ 移动结束（走出边界或遇到以前走过的点）时，该次移动的序号。（如果是遇到以前走过的点，还需知道该点的序号） 设计数据结构 主要信息： int data100100; /存放地图 int place; /当前序号 int m,n; /矩阵大小 int begin; /起始位置,方法： 按照地图及初态移动机器人直到满足结束条件：下一个要经过的点（row，line）满足（row=m | line= n) 或 datarowline 0.用place +标记刚走过的点。

3、如果走出地图输出：place 1 step(s) to exit 。 否则输出：datarowline-1 step(s) before a loop of place-datarow line step(s),运行演示,运行演示,运行演示,运行演示,满足结束条件：col 0 输出：10 step(s) to exit,同理Grid2结束状态为：,Robot Motion 程序,#include using namespace std; int data100100; / 地图 int place; / 当前位置 int m,n,begin; / 地图大小，初始位置 void move(int

4、 row,int col)；/按要求移动机器人 int main() return 0; ,Robot Motion 程序(续),int main() char ch; while( (cinmnbegin) /end of main,Robot Motion 程序(续),void move(int row,int col) bool notExit=true; while( notExit /end of move,结论：一个简洁高效的算法在很大程度上依赖于数据结构的建立。这也往往是做好一个模拟题的重点。,枚举算法及举例,核心思想：通过列举所有情况然后逐一判断，从而得到结果。从本质上看，就是

5、把问题用一定的数据结构描述，然后用某种方式遍历它，以寻求问题的解。,一个简单的例子,Zero Sum （USACO 36） 问题描述： 给定一个整数N（3=N=9)。在序列1N中插入， ，构造表达式。按字典序输出所有使得表达式为0的情况。,问题分析,在1.N中插入， 一共有多少中插法？ 考虑最坏情况N9 时，有 38 6561 种情况 这个解空间比较小，这就意味着我们可以列举所有情况看它是否满足“使得表达式为0”,选择变量： string digital = 11223344556677889; int n; 思路：输入n后把digital中2*n 1 后剔除，并在奇数位置按字典序枚举各种插入

6、情况。对每种情况如果表达式值为0，则输出之。,Zero Sum 的枚举法实现,#include #include #include using namespace std; ifstream fin(zerosum.in); Ofstream fout(zerosum.out); string digital = 11223344556677889; int n; /问题规模 int check()；/ 检查表达式是否为0 void proc(int t)；/确定第t处应插入什么字符 int main() finn; /输入问题规模 digital.resize(2*n -1); /剔除2*n

7、-1后边的元素 proc(0); return 0; ,Zero Sum 的枚举法实现,void proc(int t) if(t = n - 1) /已经插入完毕 /如果和为0则输出 if (check() = 0) foutdigitalendl; return ; /确定要插入字母在digital中的位置 int i = 2 * t + 1; digitali = ; /插入 （依字母序） proc(t + 1); /在下一个位置插入 digitali = +; proc(t + 1); digitali = -; proc(t + 1); ,Zero Sum 的枚举法实现,int ch

8、eck() /*去处插入字符后digital中的 ， 并存入teamp中*/ string teamp; for(int i = 0; i */ istringstream ssin(teamp);,int sum; ssin sum; char ch; while(ssinch) int t; ssint; if(ch = -) sum -= t; else sum += t; return sum; ,枚举的特点,枚举的特点简明但低效 只要有合适的搜索规则，就能设计出枚举算法，就可以解决几乎所有的问题。这是一种普遍适用的解题策略。 枚举算法的普遍性换来的代价是低效，由于它要考虑所有可能的情

9、况，如果问题的规模很大，情况很多，算法难免耗时过长。如果对算法进行优化，精简枚举范围，就有可能在可接受的时间内得出结果。,重点提示,虽然枚举在理论上可以解决绝大部分优化问题，然而当问题规模较大时其速度是相当差的。 然而枚举法的用处比我们想象的要大。在问题毫无头绪的情况下，枚举往往可以为我们打开一个缺口。,贪心算法及应用,贪心法的基本思想是每次选择一个局部最优策略来实施，而不考虑对今后的影响，一般来说，其时间复杂度较低。对很多题目，用贪心法并不能得到最优解，该方法的另一个难点是比较难以证明其最优性。但是，如果能证明当前策略至少不比其他策略差，就可以继续做下去。,贪心法的基本要素,贪心选择性质 所

10、求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。,Mixing Milk（usaco76）,问题描述 某商人欲从M个农民那里购买N公斤牛奶。给定整数M，N及若干个农民拥有牛奶的价格和总量。问他最少需要多少钱可以购买N公斤牛奶。 INPUT FORMAT Line 1: Two integers, N and M. The first value, N, (0 = N = 2,000,000) is the amount of milk that Merry Milk Makers want

11、 per day. The second, M, (0 = M = 5,000) is the number of farmers that they may buy from. Lines 2 through M+1: The next M lines each contain two integers, Pi and Ai. Pi (0 = Pi = 1,000) is price in cents that farmer i charges.Ai (0 = Ai = 2,000,000) is the amount of milk that farmer i can sell to Me

12、rry Milk Makers per day.,Sample Input 100 5 5 20 9 40 3 10 8 80 6 30 Output 630,问题分析,用贪心法的关键是找到最优的度量标准 既然本题要求花钱最小，我们就可以选择牛奶的价格为度量标准。 思考：该问题的最优子结构性质和贪心选择性质？,解题方法： 对每个农民按其牛奶价格进行排序，每次选择价格最低的。如果还没有买够就向该农民购买。,Mixing Milk 实例,问题：N 100，M 5，price 5,9,3,8,6, num = 20,40,10,80,30,20公斤,30公斤,40公斤,实现代码,#include #

13、include #include using namespace std; ifstream fin(milk.in); ofstream fout(milk.out); struct IntPair IntPair(int a = 0, int b = 0) first = a, second = b; int first, second; ;,/比较谓词 bool small(IntPair i1,IntPair i2)return i1.first ,实现代码续,int cost(vector / end of cost,贪心算法的抽象化控制机制,Procedure GREEDY(A,n

14、) solution NULL for i 1 to n do x select(A) if feasible(solution, x) then solution UNION(solution,x) endif repeat End GREEDY,枚举贪心,“在问题毫无头绪的情况下，枚举往往可以为我们打开一个缺口，使得其他算法可以成功。” 下面看一个例子：,Extended Lights Out (zju 1354),有一个5行6列的按钮阵列，每个按钮有一盏灯，当它被按下，它和它相邻四个(上下左右)的灯状态改变一次(亮-灭 或灭-亮) 现在给出了这个阵列的初始亮灭状态，找一种操作让灯全灭。,

15、分析,显然按键是顺序无关的，而且最多按一次(按两次相当于不按)。 最直接的想法：30个按键，每个有两种操作选择，总共要枚举230 1073741824种方案。本题时限1秒，此方法行不通。,进一步分析,考虑如图所示的操作：,点击 第2行第2列,进一步分析,考虑如图所示的操作：,X,X,点击第2行第2列,点击 第2行第3列,进一步分析,考虑如图所示的操作：,X,X,X,点击第2行第2列 点击第2行第3列,点击 第2行第5列,X,X,X,进一步分析,考虑如图所示的操作：,点击第2行第2列 点击第2行第3列 点击第2行第5列,进一步分析,只有在第2行的操作才能使第1行全灭。 在3、4、5行的操作对1行

16、完全没影响。,X,X,X,点击2行2列 点击2行3列 点击2行5列,进一步分析,如果第2行的操作没有使第1行全灭， 则后面对3、4、5行进行的操作都是瞎忙乎。,X,X,点击2行2列 点击2行3列,进一步分析,这也说明第2行的操作受第1行亮灭的情况约束。 如果第1行某列亮着，则在它的下一行同一列点击。,X,X,X,点击2行2列 点击2行3列 点击2行5列,进一步分析,保证了第1行全灭，第2行未必全灭， 于是需要第3行的操作。,X,X,X,X,进一步分析,后面各行的操作都受其上一行约束,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,进一步分析,各行操作结束后，判断最后一行是否

17、全灭。 全灭，则答案就找到了；否则考虑改变第1行。,X,X,X,X,X,X,X,X,进一步分析,因为只有第1行的操作没有约束。,X,X,X,X,X,X,X,X,解决,毫无疑问，搜索之。第1行有6个格，每格点或不点，共2664种状态。 不再是起初凭直觉的遍历1073741824个状态，效率大大提高了。 要是按列来考虑，第1列有5个格，搜索2532个状态就可以了。,程序实现,#include #include void process();/求解的过程 void press(int,int);/处理按键的过程 void output();/输出结果 int lights56;/记录灯状态，0灭，1

18、亮 int ans56;/记录结果，若在x行y列点击，ansx-1y-1=1 int main() /主函数 int n; cinn; for(int i=1;i=n;i+) cout PUZZLE # iendl; process(); /求解过程 ,程序实现,void press(int x,int y) /处理按键的过程 ansxy = 1;/记录操作 lightsxy = 1-lightsxy;/0-1，1-0 if(x0) lightsx-1y = 1-lightsx-1y; if(y0) lightsxy-1 = 1-lightsxy-1; if(x4) lightsx+1y =

19、1-lightsx+1y; if(y5) lightsxy+1 = 1-lightsxy+1; ,void process() int x,y,z,temp56; for(x=0;xtemp56; for(z=0; z=6) output(); break; /是,输出结果，结束搜索 ,void process() int x,y,z,temp56; for(x=0;xtemp56; for(z=0; z=6) output();break; ,假设z=001010 当y=3,1左移3位等于1000，两数按位求与: 001010 for(x=0;xtemp56; for(z=0;z=6) ou

20、tput();break; ,void process() int x,y,z,temp56; for(x=0;xtemp56; for(z=0;z=6) output();break; /是,输出结果，结束搜索 ,void process() int x,y,z,temp56; for(x=0;xtemp56; for(z=0;z=6) output();break; ,程序实现,void output() int x,y; for(x=0;x5;x+) coutansx0; for(y=1;y6;y+) cout ansxy; cout endl; ,解决,搜索得到的解：,X,X,X,X,

21、X,X,解决,搜索得到的解：,X,X,X,X,X,X,X,X,X,X,X,X,X,X,解决,搜索得到的解：,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,解决,搜索得到的解：,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,X,解决,搜索得到的解：,X,X,X,X,X,X,X,X,X,X,X,X,X,输出: 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0,贪心应用例2,不是每个问题都能象Mixing Milk那样容易找到贪心策略。 下面看一个例子

22、：钓鱼(pku 1042, 算法艺术与信息学竞赛P13,例题1) 在一条水平路边，有n(2=n=25)个湖，从左到右序号为1,2,3n。佳佳有H个小时的空余时间，他希望用这些时间钓鱼。他从1号湖出发向右走，有选择地在一些湖边停留一定的时间来钓鱼，最后在某个湖边结束钓鱼。他已测出，从第i个湖到第i+1个湖要走5*Ti分钟的路。他还测出，在第i个湖的第一个5分钟可钓鱼Fi条，以后每5分钟鱼量减少Di。假定没有其他人钓鱼，也不受其他因素影响，编程求出佳佳钓鱼最多的方案。,贪心应用例2,题意描述： 佳佳在每个湖中每5分钟钓的鱼数（此题中以5分钟作为单位时间），随时间的增长而线性递减。而每个湖中头5分钟

23、可以钓到的鱼数以及每个湖中相邻5分钟钓鱼数的减少量，input中均会给出。并且佳佳从任意一个湖走到它下一个湖的时间input中也都给出。,贪心应用例2,问题： 求一种方案，使得john在有限的h小时中可以钓到尽可能多的鱼。 output中需包括john在所有湖边所呆的时间，以及最后总的钓鱼数。,问题分析,我们不能简单地以某个5分钟可钓到的鱼最多为贪心标准。因为到达各个湖的额外耗时是不同的，该耗时不仅与离初始点的距离有关，还与左边紧邻的上一个钓鱼点有关。这个花费会增加到钓鱼的耗时中去。许多情况下用贪心法很难找到某个时刻的最优方案。,问题转化,问题分析： 先考虑下面问题： 佳佳不能从任意湖结束他的

24、行程，他必须一直钓到最后一个湖。 那么应该怎么做呢？,问题转化,由于每个湖都必须经过，且只经过一次，所以佳佳花在路中的总时间是确定的。 在这个条件下，可以看成佳佳学会了“瞬间移动”，即：他可以在任何时间，移动到任何他想去的湖，而移动的过程不耗时间。 于是，佳佳只需在每个5分钟的开始“瞬间移动”到当前5分钟中能钓到最多的鱼的湖，且只钓5分钟的鱼。 这样可以保证佳佳钓到尽可能多的鱼。,问题转化,回到最初的问题： 只要枚举佳佳的行程是从第一个湖到第k个湖（1=k=n）,比较出最大的钓鱼数，就是题目所求的最佳方案。 时间复杂度：O(kn2),解决方案,假设存在某种解决方案，在i号湖共钓鱼Ai个5分钟（

25、不一定是连续的），我们一定可找到一个使得在每个湖的钓鱼时间都连续且按湖序号递增的次序来钓鱼的方案，且不劣于此种方案。 也就是说我们可以在这种模型下寻找最优解。,枚举最后一个钓鱼的湖x。假设佳佳从湖1走到湖x，则路上花去的时间为T=T1+T2+Tx 在此前提下，可以认为他可从一个湖到另一个瞬间转移，即在任意时刻都可以从湖1到X中任选一个钓鱼，这样我们每次都可以选鱼最多的湖(贪心准则)。,请同学们试着自己编写该题的代码！,贪心 二分,枚举与贪心是两个较简单的算法，却有着非常广泛的应用，经常与其他算法结合起来使用。 Eg：Copying Books （zju2002） 这是一个任务分配问题，要求在最

26、短时间内解决问题。我们直接从输入开始说明题意。,Input and Output,以右边输入为例，第一行的2表示共有两组输入。每组输入包含任务个数和需要划分的块数。完成任务的时间由费时最多的任务块决定。 第一组的九个任务被化为3个长度分别为1500，1300，1700的块。因而耗时1700小时。 同学们可以可以自己验证一下这种划分的最优性。,Sample Input29 3100 200 300 400 500 600 700 800 9005 4100 100 100 100 100 Sample Output100 200 300 400 500 / 600 700 / 800 90010

27、0 / 100 / 100 / 100 100,解题思路,1. 给定最短时间，容易用贪心寻找copying方 案 O(n) 2. 如果对 T1 能找出贪心解，则对 T2 （T2T1) 也一定存在贪心解 ，即解区间连续有界。欲寻最小解，可采用二分法列举时间并用贪心检测，直到找到最优解。,#include #include using namespace std; int people501;/每个人的book数 int books501; bool proc(long long t, int m, int k) /*对给定时间t寻找贪心方案: 从后 向前，寻找剩余书数m,不小于剩余 人数k，pages不大于t的最长区间 */,/输出结果 void print(int k) int