成都网站建设新网创想,怎么选择一家好的网站建设公司,网站建设费无形资产,做网站的好公司贪心算法1信息学竞赛课堂贪心算法2贪心法实际生活中#xff0c;经常需要求一些问题的“可行解”和“最优解”#xff0c;这就是所谓的“最优化”问题。一般来说#xff0c;每个最优化问题都包含一组“限制条件”和一个“目标函数”#xff0c;符合限制条件的问题求解方案称…贪心算法 1 信息学竞赛课堂 贪心算法 2 贪心法 实际生活中经常需要求一些问题的“可行解”和“最优解”这就是所谓 的“最优化”问题。 一般来说每个最优化问题都包含一组“限制条件”和一个“目标函数” 符合限制条件的问题求解方案称为可行解使目标函数取得最佳值最大或最小 的可行解称为最优解。 求解最优化问题的算法很多例如穷举、搜索、动态规划等。贪心法也是求 解这类问题的一种常用方法。 信息学竞赛课堂 贪心算法 3 1. 贪心法的基本思想 贪心法是从问题的某个初始解出发采用逐步构造最优解的方法向给定的 目标前进。在每一个局部阶段都做一个“看上去”最优的决策并期望通过每 一次所做的局部最优选择产生出一个全局最优解。做出贪心决策的依据称为“贪 心策略”。要注意的是贪心策略一旦做出就不可再更改。 与递推不同的是贪心严格意义上说只是一种策略或方法而不是算法。推 进的每一步不是依据某一个固定的递推式而是做一个“当时看似最佳”的贪心 选择操作不断将问题归纳为更小的相似子问题。所以归纳、分析、选择 正确合适的贪心策略是解决贪心问题的关键。 信息学竞赛课堂 贪心算法 4 贪心算法在对问题求解时总是做出在当前看来最好的选择。也就是说不从整体最优解 出发来考虑它所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能 得到整体最优解但对范围相当广泛的许多问题都能产生整体最优解或整体最优解的近似 解。 贪心算法的基本思路如下 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每个子问题求解得到每个子问题的局部最优解。 4.把每个子问题的局部最优解合成为原来问题的一个解。 实现该算法的过程 从问题的某一初始状态出发 while 能朝给定总目标前进一步 do 求出可行解的一个解元素 由所有解元素组合成问题的一个可行解 信息学竞赛课堂 贪心算法 5 问题描述 给定n种物品和一个背包。物品i的重量是Wi其价值为Vi背包的容量为C 应如 何选择装入背包的物品 使得装入背包中物品的总价值最大? 这里在选择物品i装 入背包时可以选择物品i的一部分而不一定要全部装入背包不能重复装载。 小数背包问题 信息学竞赛课堂 贪心算法 6 现在有三种贪心策略 1)按照价值最大贪心是目标函数增长最快的但是背包容量却可能消耗的太快使得装 入背包的物品个数减少从而不能保证目标函数达到最大值。 2)按照重量最小贪心使得背包增长最慢很显然重量和价值没有关系这也无法保证 目标函数达到最大值。 3)按照价值率价值除以质量使得单位重量价值增长最快。保证了价值和重量是最 优解。 信息学竞赛课堂 贪心算法 7 假定n3, C20, v(25, 24, 15), w (18, 15, 10)列举4个可行解 也就是说如果我们按照价值最大贪心得到的解就是2如果按照重量最小贪心得 到解则是3而最优解是4 x1 x2 x3 Σwixi Σvixi 1 1/2 1/3 1/4 16.50 24.50 2 1 2/15 0 20.00 28.20 3 0 2/3 1 20.00 31.00 4 0 1 1/2 20.00 31.50 信息学竞赛课堂 贪心算法 8 问题描述 有一个箱子容量为 V同时有 n 个物品每个物品有一个体积。 现在从 n 个物品中任取若干个装入箱内也可以不取使箱子的剩余空间最 小。输出这个最小值。 输入格式 第一行共一个整数 V表示箱子容量。 第二行共一个整数 n表示物品总数。 接下来 n 行每行有一个正整数表示第 i 个物品的体积。 输出格式 共一行一个整数表示箱子最小剩余空间。 说明/提示 对于 100% 数据满足 0n≤301≤V≤20000。 装箱问题 输入样例 24 6 8 3 12 7 9 7 输出样例 0 #includeiostream using namespace std; int n,m,f[20005],w[35]; int main(){ cinmn; for(int i1;in;i) cinw[i]; for(int i1;in;i){ for(int jm;jw[i];j--){ if(f[j]f[j-w[i]]w[i]){ f[j]f[j-w[i]]w[i]; } } } coutm-f[m]; return 0; } 9 信息学竞赛课堂 贪心算法 10 问题描述 有若干个体积为VV10000的箱子有n(n1000)个物品v0 ,v1 ,v2… …vn vi V 。要求将所有的物品都装入箱子里使打开的箱子尽可能的少输 出打开的箱子数。 输入格式 第一行共2个整数n和 V表示物品的个数和箱子容量。 第二行共n个整数 表示每个物品的体积。 输出格式 输出一个整数表示打开的箱子总个数。 新装箱问题 输入样例 3 100 10 20 80 输出样例 2 设置贪心准则 1、将所有的物品按照体积降序排列 2、每次取出一个物品为当前未装箱的体积最大的遍历所有已经打开的箱子尝试 将该物品装入其中一个箱子 3、如果都装不下就打开一个新箱子装入物品 11 12 #includeiostream #includealgorithm using namespace std; int n,V,v[1005],r[1005],ans; bool cmp(int a, int b) { return ab; } int main() { cinnV; for(int i1; in; i) { cinv[i]; r[i]V; } sort(v1, vn1, cmp); for(int i1; in; i) { for(int j1; jn; j) { if(v[i]r[j]){ r[j]-v[i]; break; } } } for(int i1; in; i){ if(r[i]V) ans; } coutans; return 0; } 13 经典硬币问题 某人带着3种面值的硬币去购物有1元、2元、5元的硬币数量不限 他需要支付M元问怎么支付才能使硬币数量最少 #include iostream using namespace std; #define NUM 3 const int Value[NUM] {5, 2, 1}; int main(){ int i, money; int ans[NUM]{0}; cin money; for(i 0; i NUM; i){ //求每种硬币的数量 ans[i] money/Value[i]; money money - ans[i]*Value[i]; } for(i 0; i NUM; i) coutValue[i]元硬币数ans[i]endl; return 0; } 经典硬币问题 虽然每一步选硬币的操作并没有从整体最优来考虑而是只在当前步骤选取了局部最优 但是结果是全局最优的。然而局部最优并不总是能导致全局最优。 硬币问题用贪心法一定能得到最优解吗 14 经典硬币问题 在硬币问题中如果改换一下参数就不一定能得到最优解。 例如硬币面值比较奇怪是1、2、4、5、6元支付9元如果用贪心法答案是6 2 1需要3个硬币而最优的5 4只需要2个硬币。 所以在硬币问题中用贪心法是否能得到最优跟硬币的面值有关。如果是1、2、5这 样的面值贪心是有效的而对于1、2、4、5、6这样的面值贪心是无效的。 任意面值硬币问题的求解动态规划 15 信息学竞赛课堂 贪心算法 16 矩阵内取数问题 两个例子 1、可以贪心 在N行M列的正整数矩阵中要求从每一行各选出一个数使得选出的N个数的和最大。 2、不可以贪心 在一个N*M的矩阵中每一个格子赋予一个数规定每次移动只能向上或向右。现试找出 一条路径使其从左下角至右上角所经过的权值之和最大。 3 4 6 1 2 10 信息学竞赛课堂 贪心算法 17 贪心算法的特点 1、贪心选择 所谓贪心选择是指应用统一规则将原问题变为一个相似的但规模更小的子问题而 后的每一步都是当前看似最佳的选择且这种选择只依赖于已作出的选择不依赖于未作 出的选择。 2、最优子结构 执行算法时每一次得到的结果虽然都是当前问题的最优解即局部最优解但只有满 足全局最优解包含局部最优解时才能保证最终得到的结果是最优解。 信息学竞赛课堂 贪心算法 18 独木舟 【问题描述】 旅行社计划组织一个独木舟旅行。租用的独木舟都是一样的最多乘两人而且载重有一 个限度。现在要节约费用所以要尽可能地租用最少的舟。本题的任务是读入独木舟的载 重量参加旅行的人数以及每个人的体重计算出所需要的独木舟数目。 【输入格式】 第 1 行是 w100≤w≤200表示每条独木舟最大的载重量。 第 2 行是正整数 n1≤n≤30000表示参加旅行的人数。 接下来的一行 n 个正整数 t i 5≤t i ≤w表示每个人的重量。 【输出格式】 输出一行一个数表示最少的独木舟数目。 【输入样例】 100 9 90 20 20 30 50 60 70 80 90 【输出样例】 6 信息学竞赛课堂 贪心算法 19 【分析1】 先将 n 个人按照体重 t[i] 从大到小排序。对于每个人 jj 从 1 开始如果前面已 租的独木舟无法承载他那么就重新租一个。只要设置一个数组 shipship[i] 表 示第 i个独木舟还可以承载多重初始值全部设置为 wship[i] 减去 t[j] 如果 前面有多个独木舟可以承载他某个 ship[k]1≤k≤it[j]≤ship[k]那么选择 第一个能承载的去载他就可以了并且把 ship[k] 设置成 0。最后只要输出 i 即 可。 信息学竞赛课堂 贪心算法 20 【分析2】 先按照人的体重排序。 先让最重的人上船——如果最重的人和最轻的人体重总和不超过船的承重则他 们两个占用一条船。否则因为假设最重的人的体重也不超过船的承重了最 重的人单独占一条船。转变为(n – 1)或者(n – 2)的问题了。 关键在于这种贪心策略是不是正确的 我们可以证明这种策略可以得到最优解。 1 假设最重的人和最轻的人的体重和超过了船的承重那么最优解中显然 也是最重的人单独占一条船所以这种情况下最优解和贪心策略是相同的。 信息学竞赛课堂 贪心算法 21 2 假设最重的人和最轻的人的体重和没超过船的承重。 2.1 如果最优解中最重的人单独占用一条船则可以把最轻的人也放上去 这样最优解用的船数不增加。如果最轻的人占用一条船同样我们可以把最重的 人放上去最优解船数不增。 2.2 如果最优解中最重的人x和x’占用一只船(x, x’)而最轻的人y和y’占用一只 船(y, y’)我们换成(x, y) (x’,y’) 。(x, y)显然没超过船的承重——因为我们假设就 是如此。关键看(x’, y’)。x’ y’ x’ x 因为(x’, x)没超重所以(x’,y’)也合法。 所以换一下最优解船数也不增。这样我们就证明了如果可能把最重的人和最轻 的人放在一条船上不会影响最优解。反复应用这个策略就可以把n降低为(n – 1)或者(n – 2)个人的规模从而解决这个问题。 信息学竞赛课堂 贪心算法 22 #includestdio.h #includealgorithm using namespace std; int n, m, a[30005]; int main(){ scanf(“%d%d”,m,n); //m:每条船最大载重量 n:总共n个人 for(int i0;in;i) scanf(%d,a[i]); sort(a,an); int j0,kn-1,ans0; while(jk){ if(a[j]a[k]m) { j; } k--,ans; } printf(%d\n,ans); return 0; } 信息学竞赛课堂 贪心算法 23 #includeiostream #includealgorithm using namespace std; long people[10000]; int main(){ int n,i,j,ans0; long weight; cinweight; //这个表示船的重量 cinn; //这个表示人数 for(i0;in;i) cinpeople[i]; sort(people,peoplen); for(i0,j n-1;ij;j--){ //从上往下遍历 if(people[i]people[j]weight){ ans; }else{ i; ans; } } printf(%d,ans); return 0; } 思想按从小到大先排序然后第一个和最 后一个相加如果结果比船的载重大那么 就把指向最后一个的指针往前移动一个第 一个不动船数加一然后第一个和倒数第 二个相加如果比载重小那么指向第一个 的指针往后移动一个倒数第二个指针往前 移动船数加一以此类推。 信息学竞赛课堂 贪心算法 24 不相交的区间选择问题 数轴上有n条开区间(ai , bi )选择尽量多个区间使这些 区间两两没有公共点。 首先明确一个问题如果有两个区间x, y区间x完全包含y。那么显然选x是不划 算的因为x和y最多只能选一个选x还不如选y这样不仅区间数目不会减少 而且给其他区间留出了更多的位置。这样我们按照bi从小到大的顺序给区间排 序。 贪心策略 一定要选第一个区间也就是一定要选bi最小的那一个区间。选择了第一个区间 之后可以排除所有与第一个区间相交的区间然后在剩下的区间中再选择bi最 小的区间因为这样可以给后面留下更大的空间以此类推。 区间上的问题1 信息学竞赛课堂 贪心算法 25 约翰有N(1≤N≤50000)头牛约翰的草地可以认为是一条直线每只牛只喜欢在某 个特定的范围内吃草第i头牛喜欢在区间(SiEi)吃草1≤SiEi≤1,000,000,00. 奶牛们都很自私他们不喜欢和其他奶牛共享自己喜欢吃草的领域因此约翰要 保证任意两头牛都不会共享他们喜欢吃草的领域如果奶牛i和奶牛j想要同时吃 草那么要满足SiEj或者Ei≤Sj约翰想知道在同一时刻最多可以有多少 头奶牛同时吃草 【输入格式】 第 1 行 1 个整数 n。 第 2 行到第 n 行每行两个数表示Si和Ei 之间用一个空格隔开。 【输出格式】 一行一个数同时吃草的奶牛数。 自私的放牧 【输入样例】 5 2 4 1 12 4 5 7 10 7 8 【输出样例】 3 信息学竞赛课堂 贪心算法 26 选点问题 数轴上有n个闭区间[ai ,bi ]。取尽量少的点使得每个区间内都至少有一 个点不 同区间内含的点可以是同一个 先讨论区间包含的情况由于小区间被满足时大区间一定也被满足。所以在 区间 包含的情况下大区间不需要考虑。 把所有区间按b从小到大排序b相同时可以根据题目决定是否需要取a大的 贪心策略在第一个区间最右边选点然后排除被该点标志过的所有区间然后 再在剩下的区间的第一个区间最右边选点重复之前操作。 区间上的问题2 信息学竞赛课堂 贪心算法 27 种树 题目描述一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地 区被分割成块并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每 个居民想在门前种些树并指定了三个号码BET。这三个数表示该居民想在B和E之间 最少种T棵树。当然B≤E居民必须记住在指定区不能种多于区域地块数的树所以 T≤E-Bl。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少 的树的数量。 输入格式第一行包含数据N区域的个数(0N≤30000)第二行包含H房子的数目 (0H≤5000) 下面的H行描述居民们的需要 B E T0B≤E≤30000T≤E-B1。 输出格式输出文件只有一行写有树的数目 输入样例 9 4 1 4 2 4 6 2 8 9 2 3 5 2 输出样例 5 信息学竞赛课堂 贪心算法 28 区间覆盖问题 数轴上有n个闭区间[ai,bi]选择尽量少的区间覆盖一条指定线 段[s,t]。 本题的突破口仍然是区间包含和排序扫描不过可以进行一次预处理。每个区间 在[s,t]外的部分都可以预先被切掉因为它们的存在是毫无意义的。在预处理后 在相互包含的情况下小区间显然不应该考虑。 按照左端点ai从小到大排序。如果区间1的起点不是s无解因为其他区间的 起点更大 不可能覆盖到s点否则选择起点在s左边的最长区间。选择该区间 [ai,bi]后新的起点应该设置为bi并且忽略所有区间在bi之前的部分就像预处 理一样然后选择起点在bi左边的最长区间以此类推。 区间上的问题3 信息学竞赛课堂 贪心算法 29 喷水装置 题目描述有一块草坪横向长w,纵向长为h,在它的橫向中心线上不同位置处装有 n(n10000)个点状的喷水装置每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆 都被润湿。请在给出的喷水装置中选择尽量少的喷水装置把整个草坪全部润湿。 输入格式第一行输入一个正整数N表示共有N次测试数据。每一组测试数据的第一行有 三个整数n,w,hn表示共有n个喷水装置w表示草坪的横向长度h表示草坪的纵向长度。 随后的n行都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标最左边为0ri表示 该喷水装置能覆盖的圆的半径。 输出格式每组测试数据输出一个正整数 表示共需要多少个喷水装置每个输出单独 占一行。如果不存在一种能够把整个草坪湿 润的方案请输出0。 输入样例 2 2 8 6 1 1 4 5 2 10 6 4 5 6 5 输出样例 1 2 信息学竞赛课堂 贪心算法 31 5、带限期和罚款的单位时间任务调度 【问题描述】 用n个任务每个任务都需要1个时间单位执行任务i的截止时间d[i](1din)表示要求 任务i在时间d[i]结束时必须完成误时惩罚w[i]表示若任务i未在时间d[i]结束之前完成 将导致w[i]的罚款。确定所有任务的执行顺序使得惩罚最少。 【思路点拨】 要使罚款最少我们显然应尽量完成w[i]值较大的任务。 此时我们可以将任务按w[i]从大到小排序然后按照排好的顺序依次对任务进行安排。 安排的规则是使处理任务i的时间既在d[i]之内又尽量靠后如果d[i]之内的时间都已 经排满就放弃处理此项任务。 信息学竞赛课堂 贪心算法 32 题目描述 小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者主持人为 了表彰大家的勇气先奖励每个参赛者m元。先不要太高兴因为这些钱还不一定都是 你的接下来主持人宣布了比赛规则 首先比赛时间分为n个时段(n≤500)它又给出了很多小游戏每个小游戏都必须在规 定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成则要从奖励费m元中扣 去一部分钱wiwi为自然数不同的游戏扣去的钱是不一样的。当然每个游戏本身都 很简单保证每个参赛者都能在一个时段内完成而且都必须从整时段开始。主持人只 是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者小伟很想赢得冠军 当然更想赢取最多的钱注意比赛绝对不会让参赛者赔钱! 信息学竞赛课堂 贪心算法 33 输入格式 输入共4行。第1行为m表示一开始奖励给每位参赛者的钱 第2行为n表示有n个小游戏第3行有n个数分别表示游戏1到n的规定完成期限 第4行有n个数分别表示游戏1到n不能在规定期限前完成的扣款数。 输出格式 输出仅1行。表示小伟能赢取最多的钱。 输入样例 10000 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 输出样例 9950 信息学竞赛课堂 贪心算法 34 Poker Hands 【问题描述】 奶牛贝蒂和她的朋友们正在玩一种打牌游戏一共有n堆牌第i堆牌有ai张。贝 蒂可以从第i堆到第j堆里的每一堆中各抽取一张牌要求从i到j之间没有空堆 这算作出一次牌问至少需要出多少次才能把所有堆都清空。 【输入格式】 第 1 行 1 个整数 n。 第 2 行为 n 个正整数每两个数 之间用一个空格隔开。 【输出格式】 一行一个数最少出牌次数。 【输入样例】 5 2 4 1 2 3 【输出样例】 6 信息学竞赛课堂 贪心算法 35 高低卡 【问题描述】 有 2N 张牌它们的点数分别为 1到 2N 。Bessie 拿了其中的 N 张Elsie 拿了剩 下的 N 张。Bessie 和 Elsie 会进行 K 轮游戏在每轮游戏中Bessie 和 Elsie 各 出一张牌。出了的牌不能收回。在前 N/2 轮中谁的牌点数大谁就赢在后 N/2 轮中谁的牌点数小谁就赢。已知 Elsie 每一轮会出什么牌试求 Bessie 最多能 赢多少轮。 2≤N≤50000, 保证 N 是偶数。。 【输入格式】 第 1 行 1 个整数 n。 第 2 行为 n 个正整数表示Elsie每一轮出的牌 【输出格式】 一行一个数表示Bessie赢的次数。 【输入样例】 4 1 8 4 3 【输出样例】 2 THANKS
