贪心算法的应用实例.doc

贪心算法的应用实例 例2．排队问题 【题目描述】 在一个医院B 超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（0i=n）,请求出一种排列次序，使每个人排队等候时间总和最小。 输入数据：第1行一个正整数n（你=10000》，第2行有n 个不超过 1000的正整数ti. 输出要求：n个人排队时间最小总和。 输入输出样例 输入：4 5 10 8 7 输出： 67 【算法分析】 本题贪心算法：n个人时间从小到大排序，就是这n个人最佳排队方案。求部分和的和即为所求。 反证法证明：假设有最优解序列：s1,s2…sn,如s1不是最小的Tmin，不妨设sk=Tmin,将s1与sk对调，显然，对sk之后的人无影响，对sk之前的人等待都减少了，(s1-sk)0,从而新的序列比原最优序列好，这与假设矛盾，故s1为最小时间，同理可证s2…sn依次最小。 例3．:数列极差问题 【题描述】 【题描述】 using namespace std; struct prince{ int left,right;//区间左右端点 }a[10000]; int n; int result;//存放结果中的数 int cmp(const void *a,const void *b){ return (*(prince *)a).right-(*(prince *)b).right; } int work(){ qsort(a+1,n,sizeof(a[0]),cmp);//按区间右端点由小到大排序 int i,j,k; int a1,a2; a1=a[1].right-1;a2=a[1].right;result=2; for(i=2;i=n;i++) { if(a[i].left=a1 a[i].right=a2)continue;//完全包含 if (a[i].lefta2 )//完全不包含 {a1=a[i].right-1;a2=a[i].right;result=result+2;} if (a[i].lefta1 a[i].righta2 a[i].left=a2) {a1=a2;a2=a[i].right;result++;}//只包含一个 } return result; } int main(){ freopen(range6.in,r,stdin); freopen(range6.out,w,stdout); cinn; int i; for(i=1;i=n;i++) cina[i].lefta[i].right; coutwork()endl; return 0; } 例5．骆驼商队Camel Trading 【题描述】 N。在一些城市之间有路可通，有路就有商队。但是在不同的城市之间经商所得的收益不同，在下面的这个N=4的例子中，在城市1和城市2之间进行一次交易可以获得40枚金币，在城市2和3之间交易一次可以获得50枚金币，等等。 在任意两个城市之间，这样的交易只能进行一次。因为你第二次贩运你的商品时，人们对它们就不会感兴趣了。 现在你只身来到这个大陆上，用有限的资金在每个城市中购买了一支商队。你需要想办法让你的这N支商队给你带来最大的经济收益。 任务说明 给出这个大陆的地图和每两个城市之间的贸易值（如果这两个城市之间有路可通的话），你需要指挥你的N支商队进行一次经商，使得这N支商队在这次经商中获得的总收益最大。注意：你的每支商队只能进行一次交易，即它们只能从它们所在的城市到达一个相邻的城市。当然，它们也可以不进行任何交易。 输入数据 输入文件的第一行有两个整数N（1 ( N ( 100）、M（M ( 0），分别表示这个大陆上的城市数和道路数。 接下来有M行，每行包括三个整数i、j（1 ( i,j ( N且i ( j）、v(1 ( V ( 10000)，表示一条道路的信息。其中i和j表示这条路在城市i和城市j之间，v表示沿着这条路进行一次交易所得的收益。i和j的顺序是无关的，并且任意两个城市之间最多存在一条路。 输出数据 你的输出文件应该2行，第1行包含N个整数。其中第k个整数表示你在城市k中的商队将要前往哪个城市进行交易（如果这支商队进行交易的话）或者为0（如果这支商队不进行任何交易）。第2行输出最大收益值。 输入输出样例 input.in output.out 样例图示 4 5 1 2 40 1 3 30 2 3 50 2 4 30 3 4 20 2 3 1 2 150 最大收益=40+50+30+30 【算法分析】 本题转化成模型就是：在一个无向图中，对于每个点，取一条和它相关联