谈贪心算法
- 格式：doc
- 大小：69.00 KB
- 文档页数：20
1 谈谈贪心算法 例1.背包问题 【题目描述】 这是一大家很熟悉的背包问题。给定n种货物和一个载重量为m的背包。已知第i种货物的重量为wi ,其总价值为pi，编程确定一个装货方案，使得装入背包中货物的总价值最大。输出此总价值和装货方案。 【算法分析】 0，1背包问题对每种物品只有两种选择：选和不选，可用动态规划解决。而背包问题，可以选择物品的一部分装载，这样就可以把背包装满，用贪心算法可求得最优解。采用贪心标准是：选择单位重量价值高的货物优先装入，这样才能保证背包中所装货物总价值最大。而0，1背包用贪心算法却不能得到整体最优，为什么呢？我们来看一个例子： 有一背包容量为50千克，有三种货物：
物品1重10千克；价值60元； 物品2重20千克，价值100元； 物品3重30千克；价值120元。 2
总价值：（用贪心算法） 80+100+60=240 对于0，1背包问题，贪心选择之所以不能得到最优解是因为它无法保证最终将背包装满，部分背包的 闲置使单位重量背包空间的价值降低。
例2．排队问题 【题目描述】 在一个医院B 超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（0使每个人排队等候时间总和最小。 输入数据：第1行一个正整数n（你<=10000》，第2行有n
20 20 10 3
个不超过 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．:数列极差问题 【题目描述】 在黑板上写了N个正整数做成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到 4
的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。 编程任务：对于给定的数列，编程计算出极差M。 输入输出样例： 输入： 4 2 1 4 3
输出： 13 【算法分析】 当看到此题时，我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开，着重探讨求max的问题。 下面我们以求max为例来讨论此题用贪心策略求解的合理性。 讨论：假设经（Ｎ－3）次变换后得到３个数：a ,b , max＇（max＇≥ａ≥ｂ），其中max＇是（Ｎ－２）个数经（Ｎ－３）次ｆ变换后所得的最大值，此时有两种求值方式，设其所求值分别为 z1，z2，则有：z1＝(ａ×ｂ＋１）×max＇＋１，z2＝(ａ×max＇＋１）×ｂ+１所以z1－z2＝max＇－ｂ≥０若经（Ｎ－２）次变换后所得的３个数为：ｍ，ａ，ｂ（ｍ≥ａ≥ｂ）且ｍ不为（Ｎ－２）次变换 5
后的最大值，即ｍ＜max＇则此时所求得的最大值为： z3＝（ａ×ｂ+１）×ｍ+１此时z1－z3＝(１+ａｂ）（max＇－ｍ）＞０ 所以此时不为最优解。 所以若使第ｋ（１≤ｋ≤Ｎ－１）次变换后所得值最大，必使（ｋ－１）次变换后所得值最大（符合贪心策略的特点2），在进行第ｋ次变换时，只需取在进行（ｋ－１）次变换后所得数列中的两最小数ｐ，ｑ施加ｆ操作：ｐ←ｐ×ｑ+1，ｑ←∞即可（符合贪心策略特点1），因此此题可用贪心策略求解。在求ｍin时，我们只需在每次变换的数列中找到两个最大数ｐ，ｑ施加作用 ｆ：ｐ←ｐ×ｑ+１，ｑ←-∞即可．原理同上。 这是一道两次运用贪心策略解决的一道问题，它要求选手有较高的数学推理能力。
例4．整数区间range.cpp 【题目描述】 我们定义一个整数区间[a,b],a,b是一个从a开始至b 结束的连续整数的集合。编一个程序，对给定的 n个区间，找出满足下述条件的所含元素个数最少的集合中元素的个数：对于所给定的每一个区间，都至少有两个不同的整数属于该集合。(1<=n<=10000, 0<=a<=b<=1000) 输入输出格式： 输入：第一行一个正整数n，接下来有n行，每行给定一个区 6
间的a,b值 输出：一个正整数，即满足条件的集合所包含的最少元素个数 输入输出样例 输入： 输出： 4 4 3 6 2 4 0 2 4 7 【算法分析】 本题数据规模较大，用搜索做会超时，而动态规划无从下手。考虑贪心算法。题目意思是要找一个集合，该集合中的数的个数既要少又要和所给定的所有区间有交集。（每个区间至少有两个该集合中的数）。我们可以从所给的区间中选数，为了选尽量少的数，应该使所选的数和更多的区间有交集这就是贪心的标准。一开始将所有区间按照右端点从小到大排序。从第一个区间开始逐个向后检查，看所选出的数与所查看的区间有无交集，有两个则跳过，只有一个数相交，就从当前区间中选出最大的一个数（即右端点），若无交集，则从当前区间选出两个数，就（右端点，右端点-1），直至最后一个区间。 #include //整数区间问题 using namespace std; 7
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].left>a2 )//完全不包含 {a1=a[i].right-1;a2=a[i].right;result=result+2;} if (a[i].left>a1 && a[i].right>a2 && a[i].left<=a2) {a1=a2;a2=a[i].right;result++;}//只包含一个 } return result; } 8
int main(){ freopen("range6.in","r",stdin); freopen("range6.out","w",stdout); cin>>n; int i; for(i=1;i<=n;i++) cin>>a[i].left>>a[i].right; cout 例5．骆驼商队Camel Trading 【题目描述】 在一片古老的大地上，虽然商业已经非常繁荣，但是那里的人们仍然延续着古老的交易方式。他们牵着骆驼在城市之间往来奔波，贩运成批的商品，换来一袋袋的金币。 这片大陆上有N个城市，编号为1……N。在一些城市之间有路可通，有路就有商队。但是在不同的城市之间经商所得的收益不同，在下面的这个N=4的例子中，在城市1和城市2之间进行一次交易可以获得40枚金币，在城市2和3之间交易一次可以获得50枚金币，等等。 9 在任意两个城市之间，这样的交易只能进行一次。因为你第二次贩运你的商品时，人们对它们就不会感兴趣了。 现在你只身来到这个大陆上，用有限的资金在每个城市中购买了一支商队。你需要想办法让你的这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的顺序是无关的，并且任意两个城市之间最多存在一条路。 30 40 50 20 30 1 2 3 4
