。

一般来说#xff0c;每个最优化问题都包含一组“限制条件”和一个“目标函数”#xff0c;符合限制条件的问题求解方案称…贪心算法

信息学竞赛课堂

实际生活中经常需要求一些问题的“可行解”和“最优解”这就是所谓

一般来说每个最优化问题都包含一组“限制条件”和一个“目标函数”

符合限制条件的问题求解方案称为可行解使目标函数取得最佳值最大或最小

求解最优化问题的算法很多例如穷举、搜索、动态规划等。

贪心法也是求

信息学竞赛课堂

贪心法是从问题的某个初始解出发采用逐步构造最优解的方法向给定的

目标前进。

在每一个局部阶段都做一个“看上去”最优的决策并期望通过每

一次所做的局部最优选择产生出一个全局最优解。

做出贪心决策的依据称为“贪

与递推不同的是贪心严格意义上说只是一种策略或方法而不是算法。

推

进的每一步不是依据某一个固定的递推式而是做一个“当时看似最佳”的贪心

选择操作不断将问题归纳为更小的相似子问题。

所以归纳、分析、选择

信息学竞赛课堂

贪心算法在对问题求解时总是做出在当前看来最好的选择。

也就是说不从整体最优解

出发来考虑它所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能

得到整体最优解但对范围相当广泛的许多问题都能产生整体最优解或整体最优解的近似

while

给定n种物品和一个背包。

物品i的重量是Wi其价值为Vi背包的容量为C

这里在选择物品i装

入背包时可以选择物品i的一部分而不一定要全部装入背包不能重复装载。

小数背包问题

1)按照价值最大贪心是目标函数增长最快的但是背包容量却可能消耗的太快使得装

2)按照重量最小贪心使得背包增长最慢很显然重量和价值没有关系这也无法保证

3)按照价值率价值除以质量使得单位重量价值增长最快。

保证了价值和重量是最

信息学竞赛课堂

也就是说如果我们按照价值最大贪心得到的解就是2如果按照重量最小贪心得

Σwixi

有若干个体积为VV10000的箱子有n(n1000)个物品v0

,v1

2、每次取出一个物品为当前未装箱的体积最大的遍历所有已经打开的箱子尝试

将该物品装入其中一个箱子

虽然每一步选硬币的操作并没有从整体最优来考虑而是只在当前步骤选取了局部最优

硬币问题用贪心法一定能得到最优解吗

例如硬币面值比较奇怪是1、2、4、5、6元支付9元如果用贪心法答案是6

所以在硬币问题中用贪心法是否能得到最优跟硬币的面值有关。

如果是1、2、5这

样的面值贪心是有效的而对于1、2、4、5、6这样的面值贪心是无效的。

信息学竞赛课堂

在N行M列的正整数矩阵中要求从每一行各选出一个数使得选出的N个数的和最大。

在一个N*M的矩阵中每一个格子赋予一个数规定每次移动只能向上或向右。

现试找出

信息学竞赛课堂

所谓贪心选择是指应用统一规则将原问题变为一个相似的但规模更小的子问题而

后的每一步都是当前看似最佳的选择且这种选择只依赖于已作出的选择不依赖于未作

2、最优子结构

执行算法时每一次得到的结果虽然都是当前问题的最优解即局部最优解但只有满

信息学竞赛课堂

旅行社计划组织一个独木舟旅行。

租用的独木舟都是一样的最多乘两人而且载重有一

个限度。

现在要节约费用所以要尽可能地租用最少的舟。

本题的任务是读入独木舟的载

【输入格式】

先让最重的人上船——如果最重的人和最轻的人体重总和不超过船的承重则他

们两个占用一条船。

否则因为假设最重的人的体重也不超过船的承重了最

1)或者(n

也是最重的人单独占一条船所以这种情况下最优解和贪心策略是相同的。

信息学竞赛课堂

这样最优解用的船数不增加。

如果最轻的人占用一条船同样我们可以把最重的

2.2

所以换一下最优解船数也不增。

这样我们就证明了如果可能把最重的人和最轻

的人放在一条船上不会影响最优解。

反复应用这个策略就可以把n降低为(n

1)或者(n

算的因为x和y最多只能选一个选x还不如选y这样不仅区间数目不会减少

而且给其他区间留出了更多的位置。

这样我们按照bi从小到大的顺序给区间排

贪心策略

一定要选第一个区间也就是一定要选bi最小的那一个区间。

选择了第一个区间

之后可以排除所有与第一个区间相交的区间然后在剩下的区间中再选择bi最

信息学竞赛课堂

约翰有N(1≤N≤50000)头牛约翰的草地可以认为是一条直线每只牛只喜欢在某

个特定的范围内吃草第i头牛喜欢在区间(SiEi)吃草1≤SiEi≤1,000,000,00.

奶牛们都很自私他们不喜欢和其他奶牛共享自己喜欢吃草的领域因此约翰要

保证任意两头牛都不会共享他们喜欢吃草的领域如果奶牛i和奶牛j想要同时吃

草那么要满足SiEj或者Ei≤Sj约翰想知道在同一时刻最多可以有多少

头奶牛同时吃草

先讨论区间包含的情况由于小区间被满足时大区间一定也被满足。

所以在

把所有区间按b从小到大排序b相同时可以根据题目决定是否需要取a大的

贪心策略在第一个区间最右边选点然后排除被该点标志过的所有区间然后

信息学竞赛课堂

题目描述一条街的一边有几座房子。

因为环保原因居民想要在路边种些树。

路边的地

区被分割成块并被编号成1..N。

每个部分为一个单位尺寸大小并最多可种一棵树。

每

个居民想在门前种些树并指定了三个号码BET。

这三个数表示该居民想在B和E之间

最少种T棵树。

当然B≤E居民必须记住在指定区不能种多于区域地块数的树所以

T≤E-Bl。

居民们想种树的各自区域可以交叉。

你的任务是求出能满足所有要求的最少

输入格式第一行包含数据N区域的个数(0N≤30000)第二行包含H房子的数目

(0H≤5000)

数轴上有n个闭区间[ai,bi]选择尽量少的区间覆盖一条指定线

本题的突破口仍然是区间包含和排序扫描不过可以进行一次预处理。

每个区间

在[s,t]外的部分都可以预先被切掉因为它们的存在是毫无意义的。

在预处理后

按照左端点ai从小到大排序。

如果区间1的起点不是s无解因为其他区间的

起点更大

[ai,bi]后新的起点应该设置为bi并且忽略所有区间在bi之前的部分就像预处

信息学竞赛课堂

题目描述有一块草坪横向长w,纵向长为h,在它的橫向中心线上不同位置处装有

n(n10000)个点状的喷水装置每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆

都被润湿。

请在给出的喷水装置中选择尽量少的喷水装置把整个草坪全部润湿。

输入格式第一行输入一个正整数N表示共有N次测试数据。

每一组测试数据的第一行有

三个整数n,w,hn表示共有n个喷水装置w表示草坪的横向长度h表示草坪的纵向长度。

随后的n行都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标最左边为0ri表示

输出格式每组测试数据输出一个正整数

用n个任务每个任务都需要1个时间单位执行任务i的截止时间d[i](1din)表示要求

任务i在时间d[i]结束时必须完成误时惩罚w[i]表示若任务i未在时间d[i]结束之前完成

【思路点拨】

此时我们可以将任务按w[i]从大到小排序然后按照排好的顺序依次对任务进行安排。

安排的规则是使处理任务i的时间既在d[i]之内又尽量靠后如果d[i]之内的时间都已

信息学竞赛课堂

小伟报名参加中央电视台的智力大冲浪节目。

本次挑战赛吸引了众多参赛者主持人为

了表彰大家的勇气先奖励每个参赛者m元。

先不要太高兴因为这些钱还不一定都是

首先比赛时间分为n个时段(n≤500)它又给出了很多小游戏每个小游戏都必须在规

定期限ti前完成(1≤ti≤n)。

如果一个游戏没能在规定期限前完成则要从奖励费m元中扣

去一部分钱wiwi为自然数不同的游戏扣去的钱是不一样的。

当然每个游戏本身都

很简单保证每个参赛者都能在一个时段内完成而且都必须从整时段开始。

主持人只

是想考考每个参赛者如何安排组织自己做游戏的顺序。

作为参赛者小伟很想赢得冠军

信息学竞赛课堂

第2行为n表示有n个小游戏第3行有n个数分别表示游戏1到n的规定完成期限

第4行有n个数分别表示游戏1到n不能在规定期限前完成的扣款数。

输出格式

奶牛贝蒂和她的朋友们正在玩一种打牌游戏一共有n堆牌第i堆牌有ai张。

贝

蒂可以从第i堆到第j堆里的每一堆中各抽取一张牌要求从i到j之间没有空堆

【输入格式】