浅谈贪心算法

《浅谈贪心算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、贪心算法贪心算法是一种用来求最优解的算法，主要思想是将问题分为数个步骤，用一个贪心标准逐步求出每一步骤的最优解，最终产生全局最优解。贪心算法的优点是效率高，缺点是最终产生的解不一定是最优解。1.均分绒牌（N0IP2002提壽组第1题）问題描述：有N堆纸牌，编号分别为1,2,…，No每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或

2、右边的堆上。现在要求用最少的移动次数S使每堆上纸牌数都一样多。输入格式：Na[l],a[2],…，a[N]输出格式：S算冻分析：从第1堆到第N堆纸牌，按从左到右的顺序，若第i堆纸牌数a[i]人于平均数k,则将多出的纸牌移到第1+1堆上；若a[i]小于k,则将缺少的纸牌数移到第1+1堆上（缺少的纸牌数可由右侧传递给左侧，次数相同）。例：n=4a[1..4]=461084——〉6——〉10——〉8-3-4-1（等于右给左2）（右给左4）（右给左1）嫄程序：Vara:Array[1..100]0fInteger

3、;i,n,t,s:Integer;BeginReadLn（n）;Fori:=1TonDoRead（a[i]）;Fori:=1TonDot:=t+a[i];t:=tDivn;｛求平均数｝Fori:=1Ton-1DoIfa[i]<>tThenBeginInc⑸；｛计数｝a[i+1]:=a[i+1]+(a[i]-t);End;WriteLn(s);End.在用贪心算法解题时，需要注意两方面，一是问题是否适用于贪心算法，二是应选用怎样的贪心标准。在学习贪心法时，一定要多读多练，才能进步。贪心题做得越多，理解越深，

4、思路越广，利用贪心法解题的能力也就越强。1.部分背包问題问题描述：有一个容量为n的背包，有m件物品可供选择，可以任意切割为整数个单位，它们的价值分别是v[l]—v[n],所占空间分别是w[l]—w[n],求怎样选择,所得物品总价值s最大。输入格式：n,mv[l],v⑵,…，v[n]w[l],w[2],…，w[n]输出格式：s算法分析：这是一道简单的贪心题，可利用数组k记录每个物品的单位价值，按价值排序，从人价值到小价值选择，直到剩余空间n=0。需要注意整型与实型在使用上的细节。源程序：Vara,v,w:A

5、rray[1..100]0fInteger；k:Array[1..100]0fReal;i,j,n,m,t:lnteger;h,s:Real;BeginReadLn(n,m);Fori:=1TomDoRead(v[i]);Fori:=1TomDoRead(w[i]);Fori:=1TomDok[i]:=v[i]/w[i];｛求单位价值｝Fori:=1Tom-1DoForj:=i+1TomDoIfk[i]

6、:=v[j];vD]:=t;t：=w[i];w[i]:=w[j];w[j]:=t;End;｛排序｝Fori:=1TomDoBeginIfn=0ThenBreak；剩余空间，结束｝Ifw[i]<=nThenBeginn:=n-w[i];w[i]:=0;s:=s+v[i];v[i]：=0;k[i]：=0;EndElseBegins:=s+k[i]*n;Break;End;｛两种情况｝End;WriteLn(s:0:2);End.1.牛奶问題问题描述：牛奶商总是希望花最少的成本，赚取最大的利润。在一个牛奶采购市

7、场里，冇n个农民，他们分别拥有k[l]…k[n]单位奶，单位价格分别是v[l]・・・v[n]。已知牛奶商需要m单位牛奶,假如他有无限的钱，应该怎样选择，才会花费最少的钱s。输入格式：n,mv[l],k[l]v[2],k[2]v[n],k[n]输出格式：s算法分析：这道题与上一道题类似，先排序比较单位价格，再从低价到高价选择，直到买完。源程序:Varv,k:Array[1..100]OfInteger;i,j,t,n,m:Integer;BeginReadLn(n,m);Fori:=1TonDoReadLn

8、(v[i],k[i]);Fori:=1Ton-1DoForj:=i+1TonDoIfv[i]>v[j]ThenBegint：=v[i];v[i]:=vD);v[j]:=t;t：=k[i];k[i]:=：=t;End;｛排序｝i:=0;t:=0;Whilem>0DoBeginlfi>nThenBeginWriteLn(tErrorl,);Exit;End;｛如果买完全部牛奶仍未满足,则报错｝lnc(i);Ifk[i]>=mThe