第4章_贪心算法-2016-all概要.ppt

选择n-1条边； 【贪婪准则】 从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。 3、Kruskal算法 【注意】加入边不能产生环路，否则得不到生成树 。 是一种按照网中边的权值递增的顺序构造最小生成树的方法。 按权值递增的次序选择n-1条边，每选一条边，要判断是否构成回路。 （1）设无向图连通网为G(V,E)，T为G的最小生成树，初始时T={V,Φ}（此时T中有n个连通分量）； （2）按照边的权值递增的顺序，考察E(G)中的每条边e，判断加入e后，T中的边是否构成回路； （3）依次判断E(G)中的每条边，直到T的连通分量为1时（或T的边数为n-1时），此连通分量T即为G的一棵最小生成树。 3、Kruskal算法思想 * 3.Kruskal算法 Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。 * 例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示。 删数问题 给定n位正整数a，去掉其中任意k≤n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。 输入 第1行是1个正整数a，第2行是正整数k。 输出 对于给定的正整数a，编程计算删去k个数字后得到的最小数。 * 输入样例 输出样例 1785434 13 * 删数问题 * 删数问题 string a;　　　　　　　　//n位数a int k; cinak; //如果k≥n，数字被删完了 If (k = a.size()) a.erase(); else while(k 0) { 　　//寻找最近下降点 　　int i; 　　for (i=0; (ia.size()-1) (a[i] = a[i+1]); ++i); 　　a.erase(i, 1);　　　　//删除xi 　　k- -; } //删除前导数字0 while(a.size() 1 a[0] == 0) 　　a.erase(0, 1); coutaendl; * 删数问题 旅行规划问题 G 先生想独自驾驶汽车从城市A 到城市B。从城市A 到城市B 的距离为d0 公里。汽车油箱的容量为c 公升。每公升汽油能行驶e 公里。 出发点每公升汽油的价格为p 元。从城市A到城市B 沿途有n 个加油站。第i 个加油站距出发点的距离为di，油价为每公升pi元。如何规划才能使旅行的费用最省。 旅行规划问题 编程任务：对于给定的d0、c、e、p和n， 以及n个加油站的距离和油价di 和pi，编程计算最小的旅行费用。如果无法到达目的地，输出“No Solution”。 旅行规划问题 第一步：判断旅行家能否到达目的地 假设在任一个加油站都加满油，能否到达终点 旅行规划问题 第二步：预算最少费用 采用贪心算法的思想求解 旅行规划问题 汽车在到达目的地之前的每一时刻，都必须保证油箱中的汽油足够行驶到下一油站。 如果以p(i)表示第i油站的汽油价格，x(i)表示在第i油站所加汽油的量，总费用为 P ＝ ∑p(i) * x(i) i=0,1,….,n 旅行规划问题 两个城市之间的距离是固定不变的，汽车从出发点到达目的地所需要的汽油总量（即∑x(i) i=0,1,….,n ）自然也是固定不变的。 根据使费用最少的求解目标，要使费用函数取得最优值（在此为最小值），必须使p(i)尽可能小：也就是汽车要尽可能在价格便宜的油站加油。 旅行规划问题 汽车每到达一个油站i（包括出发点第0站，但不包括目的地第n+1站），都要检查是否需要加油。 旅行规划问题 如果汽车在某个油站i需要加油，那么，就先将该油站的汽油价格p(i)与下一油站的汽油价格p(i+1)进行比较，若p(i)=p(i+1)，加油时，只需保证油箱中的汽油能够到达下一油站（第i+1站）即可； 否则，继续将p(i)与第i+2站的汽油价格p(i+2)进行比较，…… 判断是否需要在第i站加油的条件可以确定为：在到达第i站时，汽车油箱中的剩余汽油（用变量rest表示剩余汽油的多少）是否足够行驶到下一更便宜的油站j，即rest*e是否大于或等于d(j)-d(i)。 如果一