null贪心策略贪心策略引 例引 例【问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
描述】：在N行M列的正整数矩阵中,要求从每行中选出1个数,使得选出的总共N个数的和最大。
【试题
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
】：本题可用贪心策略：选n次,每一次选相应行中的最大值即可。
读入n, m,矩阵数据；
total= 0;
for (i=1;i<=n;i++) //对n行进行选择
{ 选择第i行最大的数,记为k；
total+=k；
}
输出最大总和total；
贪心算法贪心算法贪心的定义：指从问题的初始状态出发，向给定的目标推进。但不同的是，推进的每一步不是依据某一固定的递推式，而是作一个当时看似最佳的贪心策略，不断地将问题实例归纳为更小的相似的子问题，并期望通过所做的局部最优选择产生出一个全局最优解。
重点：贪心策略的选取。
贪心与递推的区别是：推进的每一步不是依据一个固定的递推式,而是做一个当时看似最优的贪心选择。null贪心是一种解题策略,也是一种解题思想
使用贪心方法需要注意局部最优与全局最优的关系,选择当前状态的局部最优并不一定能推导出问题的全局最优引例2：在一个N×M的方格阵中,每一格子赋予一个数（即为权）。规定每次移动时只能向上或向右。现试找出一条路径,使其从左下角至右上角所经过的权之和最大。
【分析】本题用贪心策略不能得到最优解,我们以2×4的矩阵为例。
若按贪心策略求解,所得路径为：1,3,4,6；
若按动态规划法求解,所得路径为：1,2,10,6。几个简单的贪心问题 几个简单的贪心问题 【最优装载问题】：给n个物体, 第i个物体重量为wi, 选择尽量多的物体, 使得总重量不超过C;
【部分背包问题】:有n个物体, 第i个物体的重量为wi, 价值为vi, 在总重量不超过C的情况下让总价值尽量高;
【乘船问题】:有n个人, 第i个人重量为wi. 每艘船的载重量为C, 最多乘两个人. 用最少的船装载所有人;
贪心策略:最优装载问题:先拿轻的 贪心策略:部分背包问题:先拿性价比高的 贪心策略:乘船问题:最轻的人和尽量重的人配对; 应用举例1---部分背包问题应用举例1---部分背包问题【问题描述】：给定一个最大载重量为M的卡车和N种食品,有食盐,白糖,大米等。已知第i种食品最多拥有Wi公斤,其商品价值为Vi元/公斤,编程确定一个装货
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
,使得装入卡车中的所有物品总价值最大。【试题分析】：因为每一个物品都可以分割成单位块,单位块的利益越大显然总收益越大,所以它局部最优满足全局最优,可以用贪心法解答,方法如下：先将单位块收益按从大到小进行排列,然后用循环从单位块收益最大的取起,直到不能取为止便得到了最优解。null问题初始化； //读入数据
按vi从大到小将商品排序；
i= 1;
While(m>=0&&i<=n)
{
if(m=0)return; //如果卡车满载则跳出循环
m=m-wi;
if(m>= 0)将第i种商品全部装入卡车；
else 将m+wi重量的物品i装入卡车;
i= i + 1; //选择下一种商品
}程序框架结构贪心策略求解的问题贪心策略求解的问题 因此,利用贪心策略解题,需要解决两个问题：
首先,确定问题是否能用贪心策略求解；一般来说,适用于贪心策略求解的问题具有以下特点：
1.可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题,一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后,原问题将变成一个相似的,但规模更小的问题,而后的每一步都是当前看似最佳的选择,且每一个选择都仅做一次。
2.原问题的最优解包含子问题的最优解,即问题具有最优子结构的性质。在背包问题中,第一次选择单位质量最大的货物,它是第一个子问题的最优解,第二次选择剩下的货物中单位重量价值最大的货物,同样是第二个子问题的最优解,依次类推。
其次,如何选择一个贪心
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
？正确的贪心标准可以得到问题的最优解,在确定采用贪心策略解决问题时,不能随意的判断贪心标准是否正确,尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。应用举例2---删数问题应用举例2---删数问题【问题描述】：键盘输入一 个高精度的正整数n（n<=240位）,去掉其中任意s个数字后剩下的数字按照原来的次序将组成一个新的正整数。编程对给定的n和s,寻求一种方案,使得剩下组成的新数最小。
输入：178546
4
输出：14null贪心策略：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则输出最后一个数字；否则删除第一个递减区间的首字符，这样删一位便形成了一个新数字串。然后回到串首，按上述规则再删下一个数字。重复上述过程s次为止，剩下的数字便是问题的解。
N=178546
=17546
=1546
=146
=14nullcin>>s>>m;
n=s.length();
for(i=0;i
s[j+1])//删除第一个递减区间的首字符
{
for(k=j;kj；
void solve()
{ int i=1,j=n,pair=0;
while(i>max>>n;
for(i=1;i<=n;i++)
{cin>>p;a[p]++;}//桶排序
for(i=max;i>=1;i--)//分组
while(a[i])
{ a[i]--;t++;
for(j=max-i;j>0;j--)
if(a[j]){a[j]--;break;}
}
cout< 从 ③ 取 3 张牌放到 ②（9 11 10 10）-> 从 ② 取 1 张牌放到①（10 10 10 10）。
[输 入]：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）
[输 出]：所有堆均达到相等时的最少移动次数。‘
[输入输出样例] 4 9 8 17 6 屏慕显示： 3应用举例8---均分纸牌应用举例8---均分纸牌【试题分析】我们要使移动次数最少，就是要把浪费降至零。通过对具体情况的分析，可以看出在某相邻的两堆之间移动两次或两次以上，是一种浪费，因为我们可以把它们合并为一次或零次。因此，我们将相邻两堆间的移动次数限定在一次或零次。应用举例7---均分纸牌应用举例7---均分纸牌【分析】如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！拿例题来说，平均张数为10,原张数9，8，17，6，变为-1，-2，7，-4，其中没有为0的数，我们从左边出发：要使第1堆的牌数-1变为0，只须将-1张牌移到它的右边（第2堆）-2中；结果是-1变为0，-2变为-3，各堆牌张数变为0，-3，7，-4；同理：要使第2堆变为0，只需将-3移到它的右边（第3堆）中去，各堆牌张数变为0，0，4，-4；要使第3堆变为0，只需将第3堆中的4移到它的右边（第4堆）中去，结果为0，0，0，0，完成任务。每移动1次牌，步数加1。也许你要问，负数张牌怎么移，不违反题意吗？其实从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆，步数是一样的。
如果张数中本来就有为0的，怎么办呢？如0，-1，-5，6，还是从左算起（从右算起也完全一样），第1堆是0，无需移牌，余下与上相同；再比如-1，-2，3，10，-4，-6，从左算起，第1次移动的结果为0，-3，3，10，-4，-6；第2次移动的结果为0，0，0，10，-4，-6，现在第3堆已经变为0了，可节省1步，余下继续。贪心的经典应用贪心的经典应用一、不相交的区间选择一、不相交的区间选择• 给n个开区间[Si,Fi], 选择尽量多的区间, 使得两两不交。
• 算法: 首先按照结束时间f1<=f2<…<=fn的顺序排序,依次考虑各个活动, 如果没有和已经选择的活动冲突, 就选; 否则就不选。
• 正确性: 如果不选f1, 假设第一个选择的是fi,则如果fi和f1不交叉则多选一个f1更划算; 如果交叉则把fi换成f1不影响后续选择。【培训试题】活动选择1649 【培训试题】活动选择1649 Description
学校在最近几天有n个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。 现在给出n个活动使用礼堂的起始时间Bi和结束时间Ei(Bi < Ei)，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。
Input
第一行一个整数n(n<=1000)； 接下来的n行，每行两个整数，第一个Bi，第二个是Ei(Bi< Ei <=32767)
Output：
输出最多能安排的活动个数。nullSample Input
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13
Sample Output：4二、区间选点二、区间选点• 给n个闭区间[ai,bi], 在数轴上选尽量少的点,使每个区间内至少有一个点。分析：如果可以按照所有区间的结束位置排序,结束位置相同的项,开始位置小的项在前面。从区间1到区间n进行循环,对于当前区间,若集合中的数不能覆盖它,则从区间末尾向前扫描,若当前数没在集合中出现,则将该数加入集合,直至使集合能覆盖该区间为止。【培训试题】整数区间1650 【培训试题】整数区间1650 Description：
一个整数区间[A,B],A 请编程完成以下任务： 1.从文件中读取区间的个数及其它们的描述； 2.找到满足下述条件的所含元素个数最少的集合中元素的个数,对于每一个区间,都至少有两个不同的整数属于该集合。
Input：首行包括区间的数目n,1<=n<=10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0<=a<=b<=10000,它们是某一个区间的开始值和结束值。
Output：第一行集合元素的个数,对于每一个区间都至少有两个不同的整数属于该区间,且集合所包含元素数目最少。
Sample Input：
4
3 6
2 4
0 2
4 7
Sample Output:4null三、区间覆盖三、区间覆盖• 给n个闭区间[ai,bi], 选择尽量少的区间覆盖一个给定线段[s, f]。
• 算法: 对于每个区间, 删除在[s, f]之外的部分, 并按a1<=a2<…<=an的顺序排序, a相同时按b从大到小排序. 从左到右扫描, 如果当前区间可以覆盖新的部分, 选择此线段。【培训试题】线段覆盖1893 【培训试题】线段覆盖1893 Description:
给出数轴上N条线段,第i条线段用两个数表示Ai,Bi(Ai=b的作业集合, 将N1的作业按a非减序排序, N2中的作业按照b非增序排序, 则N1作业接N2作业构成最优顺序.
• 程序易于实现, 时间O(nlogn), 关键在于正确性证明。null例：加工生产调度
【问题描述】：某工厂收到了n个产品的订单,这n个产品分别在A、B两个车间加工,并且必须先在A车间加工后才可以到B车间加工。
某个产品i在A、B两车间加工的时间分别为Ai、Bi。怎样安排这n个产品的加工顺序,才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在A、B两车间加工完毕的时间。
【输入】：第一行仅—个数据n(0
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
出这样的贪心法：
设Mi=min{ai, bi}
将M按照从小到大的顺序排序。然后从第1个开始处理，若Mi=ai，则将它排在从头开始的已经作业后面，若Mi=bi，则将它排在从尾开始的作业前面。null例如：N=5
（a1，a2，a3，a4，a5）=（3，5，8，7，10）
（b1，b2，b3，b4，b5）=（6，2，1，4，9）
则（m1，m2，m3，m4，m5）=（3，2，1，4，9）
排序之后为（m3，m2，m1，m4，m5）
处理m3：∵m3=b3 ∴m3排在后面；加入m3之后的加工顺序为( ， ， ， ，3)；
处理m2：∵m2=b2 ∴m2排在后面；加入m2之后的加工顺序为( ， ， ，2，3)；
处理m1：∵m3=a1 ∴m1排在前面；加入m1之后的加工顺序为(1， ， ，2，3)；
处理m4：∵m4=b4 ∴m4排在后面；加入m4之后的加工顺序为(1， ，4，2，3)；
处理m5：∵m5=b5 ∴m5排在后面；加入m5之后的加工顺序为(1，5，4，2，3)；
则最优加工顺序就是（1，5，4，2，3），最短时间为34。显然这是最优解。
问题是这种贪心策略是否正确呢？还需证明。 null算法流程如下：
for I := 1 to N do {求M数组}
if A[I] < B[I] then M[I] := A[I]
else M[I] := B[I]；
将M从小到大排序；
S := 1; T := N; {首位指针初始化}
for I := 1 to N do
if 对于第I小的工序J，若A[J] < B[J] then
begin
Order[S] := J; {将工序J插在加工序列的前面}
S := S + 1;
end
else begin
Order[T] := J; {将工序J插在加工序列的后面}
T := T - 1;
end;五、任务时间表问题五、任务时间表问题• 有n个任务, 每个任务都需要1个时间单位执行. 任务i的截止时di(1<=di<=n)表示要求任务i在时间di前结束. 误时惩罚wi表示若任务i未在时间di之前结束将导致wi的惩罚;
• 确定所有任务的执行顺序, 使得最惩罚最小;null分析：• 称在限期内完成的任务为早任务, 收到罚款的任务为迟任务. 如果早任务紧跟在迟任务之后, 交换之后总罚款不变；
• 假设对于相邻两个早任务i和i+1. 由于两个任务都是早任务, 因此t j+1<=dj+1. 若di>di+1,则ti+1<=di+1>n;
for(i=1;i<=n;i++) {cin>>m;c[m]++;b[i]=2000000000;}
m=0;
for(i=1;i<=20000;i++)
while(c[i]) {a[++m]=i;c[i]--;}
for(i=1;i<=n-1;i++)
{ minn=2000000000;
if(a[x]+a[x+1]
本文档为【算法导论-贪心算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483