当前位置:首页 >> 学科竞赛 >>

pascal算法讲义第十讲


百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

第十讲 贪心算法
一、 贪心初步
贪心法是一种解决最优问题的策略。它是从问题的初始解出发, 按照当前最佳的选择,把问题归纳为更小的相似的子问题,并使子问 题最优,再由子问题来推导出全局最优解。 使用贪心方法需要注意局部最优与全局最优的关系,选择当前状 态的局部最优

并不一定能推导出问题的全局最优。 【引例】在一个 N×M 的方格阵中,每一格子赋予一个数值,规定每 次移动时只能向上或向右。现试找出一条路径,使其从左下角至右上 角所经过的数字之和最大。 我们以 2×3 的矩阵为例:

若按贪心策略求解,所得路径为:1→3→4→6; 若按动态规划求解,所得路径为:1→2→10→6。 动态规划算法会在 2.3.4 详细介绍。

二、 贪心策略的特点
1. 贪心选择性质: 算法中每一步选择都是当前看似最佳的选择, 这种 选择依赖于已做出的选择,但不依赖于未做的选择。

第 1 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

2.最优子结构性质:算法中每一次都取得了最优解(即局部最优解), 要保证最后的结果最优,则必须满足全局最优解包含局部最优解。 但并不是所有具有最优子结构的问题都可以用贪心策略求解。 因为贪 心往往是盲目的,需要使用更理性的方法——动态规划(例如“0-1 背 包问题”与“部分背包问题”)同时有些具有最优子结构的问题只能用 贪心而不能用动态规划解。

问题 1:部分背包问题 给定一个最大载重量为 M 的卡车和 N 种食品,有食盐,白糖,大米 等。已知第 i 种食品的最多拥有 Wi 公斤,其商品价值为 Vi 元/公斤, 编程确定一个装货方案,使得装入卡车中的所有物品总价值最大。 【分析】因为每一个物品都可以分割成单位块,单位块的利益越大, 显然总收益越大, 所以它局部最优满足全局最优, 可以用贪心法解答。 方法如下:先将单位块收益按从大到小进行排列,然后用循环从单位 块收益最大的取起,直到不能取为止便得到了最优解。

问题 2:0/1 背包问题 给定一个最大载重量为 M 的卡车和 N 种动物。已知第 i 种动物的重 量为 Wi,其最大价值为 Vi,设定 M,Wi,Vi 均为整数,编程确定一 个装货方案,使得装入卡车中的所有动物总价值最大。 【分析】按贪心法:每次选价格最大的装载。很明显有反例:设 N=3, 卡车最大载重量是 100,三种动物 A、B、C 的重量分别是 40,50,70,其
第 2 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

对应的总价值分别是 80、100、150。

三、 贪心策略与其他算法的区别
1.贪心与递推:与递推不同的是,贪心法中推进的每一步不是依据某 一固定的递推式,而是当前看似最佳的贪心决策,不断的将问题归纳 为更加小的相似的子问题。所以归纳、分析、选择正确合适的贪心策 略,是正确解决贪心问题的关键。 2.贪心与动态规划:与动态规划不同的是,贪心是鼠目寸光;动态规 划是统揽全局。

四、 贪心策略的证明
贪心策略能否适用,关键看在贪心的策略下,局部的最优解能否得到 全局最优解。要看是否得到最优解,就要看贪心选择特征的证明了。 常用的证明法有反证法和构造法。 1.反证法:顾名思义,对于当前的贪心策略,否定当前的选择,看看
第 3 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

是否能得到最优解,如果不能得到,说明当前贪心策略是正确的;否 则,当前策略不正确,不可用。 2.构造法:对于题目给出的问题,用贪心策略时,把问题构造成已知 的算法或数据结构,以此证明贪心策略是正确的。

五、经典贪心模型
1)最优装载问题:给 n 个物体,第 i 个物体重量为 wi,选择尽可能 量多的物体,使总重量不超过 C。 2)部分背包问题:有 n 个物体,第 i 个物体重量为 wi,价值为 vi, 在总重量不超过 C 的情况下让总价值尽量高。 3)乘船问题:有 n 个人,第 i 个人重量为 wi,每艘船的载重量为 C, 最多乘 2 人,用最少的船装载所有人。 贪心策略: 1)最优装载问题:先拿轻的 2)部分背包问题:先拿性价比高的 3)乘船问题:最轻的和尽量重的配对

例题 2.3.3.5.1:键盘输入一个高精度的正整数 n(n<=240 位),去掉其 中任意 s 个数字后剩下的数字按照原来的次序将组成一个新的正整 数。编程对给定的 n 和 s,寻求一种方案,使得剩下组成的新数最小。 【样例输入】178543 4
第 4 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

【样例输出】13 【分析】 由于正整数 n 的有效位数最大可达 240 位, 所以可以采用字符串类型 来存储 n。那么,应如何来确定该删除哪 s 位呢?是不是只要删掉最 大的 s 个数字就可以了呢? 为了尽可能地逼近目标,我们选取的贪心策略为:每一步总是选择一 个使剩下的数最小的数字删去,即按高位到低位的顺序搜索,若各位 数字递增, 则删除最后一个数字, 否则删除第一个递减区间的首字符。 然后回到串首,按上述规则再删除下一个数字。重复以上过程 s 次, 剩下的数字串便是问题的解了。 例题 2.3.3.5.2:食堂排队问题 在一个食堂,有 n 个人排队买饭,每个人买饭需要的时间为 Ti,请你 找出一种排列次序,是每个人买饭的时间总和最小。 【分析】 由题意可知,本题可以采用的贪心策略为:将 n 个人排队买饭的时间 从小到大排序,再依次累加每人的买饭时间,即可得到最小的总和。 由样例可知,排好序后的数据为(1,3,5,7,9,11),每个人的买饭时间如 下: T1=1 T2=T1+T2=1+3=4 T3=T2+T3=1+3+5=9 T4=T3+t4=1+3+5+7=16
第 5 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

T5=T4+T5=1+3+5+7+9=25 T6=T5+T6=1+3+5+7+9+11=36 总时间 T=T1+T2+T3+T4+T5+T6=91 用反证法证明如下: 假设一个不排好序的 n 个人也能得到最优答 案, 比如把(1,3,5,7,9,11)中的 3,5 对调一下, 得到的序列为(1,5,3,7,9,11)。 对调后,3,5 前后的 1,7,9,11 四个人的买饭时间不会有变化,关键的 变化是 3,5 两个人。这时,5 这个人的买饭时间为 1+5,3 这个人的买 饭时间变为 1+5+3,此时两个人的总买饭时间中,5 被累加了 2 次, 而原方案中是 3 被累加了 2 次,其他一样。由此,两者相比较,可知 有序的序列能得到最优的方案。 对于其他位置的改变可以采用同样的 方法证明。用反证法证明时,关键是证明反例不成立,由此推出原方 案是最优的。 问题推广 1:排队打水问题 【问题描述】有 n 个人在一个水龙头前排队接水,假如每个人接水的 时间为 Ti,请编程找出这 n 个人排队的一种顺序,使得这 n 个人的平 均等待时间最小。 【输入文件】输入文件共两行,第一行为 n;第二行分别表示第 1 个 人到第 n 个人每人的接水时间 T1,T2…,Tn。 【输出文件】输出文件仅一行为最小的平均等待时间。 【样例输入】 6 5 3 7 1 9 10
第 6 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

【样例输出】 15 【思路点拨】首先需要理解平均等待时间的概念。平均等待时间就是 每个人的等待时间之和再除以 n,因为 n 是个常数,所有等待时间之 和最小也就等同于平均等待时间最小。 这样就转化为前面的问题了。 问题推广 2:排队打水问题 【问题描述】有 n 个人排队到 r 个水龙头去打水,他们装满水桶的时 间 T1、T2…,Tn 为整数且各不相等,应如何安排他们的打水顺序才能 使他们总共花费的时间最少? 【文件输入】输入文件共计两行,第一行 n,r(n<=500,r<=75),第二行 为 n 个人打水所用的时间 Ti (Ti<=100); 【文件输出】输出文件只有一行为 n 个人打完水的最少总共花费时 间。 【样例输入】 32 1234 【样例输出】 13

例题 2.3.3.5.3:打包 某工厂生产出的产品都要被打包放入正四棱柱的盒子内, 所有盒子的
第 7 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

高度为 h,但地面尺寸不同,可以为 1x1、2x2、3x3、4x4、5x5、6x6。 如下图所示。

这些盒子将被放入高度为 h,地面尺寸为 6x6 的箱子中。为了降低运 送成本,工厂希望尽量减少箱子的数量。如果有一个好算法,能使箱 子的数量降到最低, 这将给工厂节省不少的资金。 请你编写一个程序。 分析:

第 8 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

例题 2.3.3.5.4:均分纸牌(NOIP2002) 有 N 堆纸牌,编号分别为 1,2,…,N。每堆上有若干张,但纸牌总数必 为 N 的倍数。可以在任一堆上取若于张纸牌,然后移动。 移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上; 在编号为 N 的堆上取的纸牌, 只能移到编号为 N-1 的堆上; 其他堆上 取的纸牌,可以移到相邻左边或右边的堆上。 现在要求找出一种移动方法, 用最少的移动次数使每堆上纸牌数都一 样多。 例如 N=4,4 堆纸牌数分别为:①9 ②8 ③17 ④6

移动 3 次可达到目的:从③取 4 张牌放到④(9 8 13 10)->从③取 3 张 牌放到②(9 11 10 10)->从②取 1 张牌放到①(10 10 10 10) 。 【文件输入】 第一行为一个整数 N(N 堆纸牌,1<=N<=100), 第二行为 n 个用空格分开的整数,依次为 A1 A2 … An(N 堆纸牌,每堆纸牌初始 数,l<=Ai<=10000)。 【文件输出】所有堆均达到相等时的最少移动次数。 【样例输入】 4 9 8 17 6 【样例输出】3 分析: 【试题分析】我们要使移动次数最少,就是要把浪费降至零。通过对 具体情况的分析, 可以看出在某相邻的两堆之间移动两次或两次以上,
第 9 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

是一种浪费,因为我们可以把它们合并为一次或零次。 【分析】 如果你想到把每堆牌的张数减去平均张数,题目就变成移动正数,加 到负数中,最终使大家都变成 0,那就意味着成功了一半! 从第 i 堆移动-m 张牌到第 i+1 堆,等价于从第 i+1 堆移动 m 张牌到第 i 堆,步数是一样的。 注意最左边的 0 和最右边的 0 不能算在内,如 0,0,1,-3,4,0,-1,0,0

思考 1: 若题目中的纸牌排成一个环状,应如何处理呢? 其中 n<=1000。

思考 2: (2011 重庆省选) 有 n 个小朋友坐成一圈,每人有 ai 个糖果。每人只能给左右两人传 递糖果。每人每次传递一个糖果代价为 1。求使所有人获得均等糖果
第 10 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

的最小代价。 【数据规模】 对于 30%的数据 n<=1000; 对于 100%的数据 n<=1000000

例题 2.3.3.5.5:射击比赛(CEOI1997) 我们假设射击的目标是一个由 R*C(2≤R≤C≤1000)个小方格组成的矩形 网格。网格中每一列恰有 2 个白色的小方格和 R-2 个黑色的小方格。 定义网格的行从顶至底编号为 1~R,列从左至右编号为 1~C。 射击者可射击 C 次。 在连续的 C 次射击中, 若每列恰好有一个白色的 方格被射中,且不存在无白色方格被射中的行,这样的射击才是正确 的。问题是,如果存在正确的射击方法,则要求找到它。 例如考虑如下目标:由上图可以看出,在每列中依次射中的行坐标为 2,3,1,4。现在要求你编程计算出是否有正确的射击方法。

根据题设条件,射击的选择有 2C 种,符合要求的却很少。要解决问
第 11 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

题,还需从正确的射击方法的特征入手。 【方法 1】网络流算法 我们将表示列的点编号为 1 到 C,表示行的点编号为 C+1 到 C+R,如 果一个白色方格处在第 i 行第 j 列,那么从点 j 向点 C+i 连一条弧,弧 的容量为 1。再增设一个源点 S,从点 S 往点 1 到 C 间各连一条弧, 弧的容量为 1,又设一个汇点 T,从点 C+1 到点 C+R 向汇点 T 连一条 弧,弧的容量为 1,那么从源点 S 到汇点 T 求最大流,求出的最大流 量即为最多可以射击到的行数。 各条流的路线则描述了具体的射击方 案。 显然,如果用网络流求出的最大流量比 R 小,则问题无解,否则我们 可以根据网络流的结果求出该二分图的具体匹配方案。

红色的连线流量为 1 黑色的连线流量为 0 选择的射击格即为: (1,3), (2,1), (3,2), (4,4)

网络流算法经过优化,时间复杂度可以达到 O(C*(n+4C+4R)) 上述网络流算法虽然可以通过全部数据,但编程复杂度很高,而且极 易出错,一不小心就会因为一个小错误影响整个程序。
第 12 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

【方法二】贪心方法 1、统计所有行包含的白格数 2、从还没有射击格的行中选出一个白格数最少的 3、检查所选的行 (1)若所选行的白格数为 0,则输出无解; (2)否则从所选行的白格中任选一个作为射击格,并将与该格同列 的另一个白格所处行的白格数减 1 4、返回到第 2 步,直到所有的行都有射击格。 5、若还有列没有选射击格,则在该列任选一白格作为射击格即可 上面的贪心方法非常高效: 时间复杂度为 O(R×C), 如果在程序中使用堆优化, 时间复杂度将降为 O(R×log2C)。空间复杂度是线性的,而且非常容易实现。 现在关键的问题就是——如何证明它的正确性? 证明: 用 h[i]表示第 i 行的白格数。如果最开始的时候: ①min{h[i]}=0:第 i 行已经没有办法找到可作为射击格的白格,那么 问题只能无解。 ②min{h[i]}=1:那么第 i 行的这一个白格必须要作为射击格,否则将 因第 i 行没有射击格而造成问题无解。 ③min{h[i]}≥2:那么在这一行任选一个白格,顶多只会造成剩余行中有 一行 h 值为 1,再处理那一行, 最多也只会再造成剩余行中有一行 h 值 为 1,如此往复,将保持 h 值为 1 的行数不超过 1 行,最后最坏的情况
第 13 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

也是造成最后一行的 h 值为 1,继续下去所有行就都已选取了射击格 了。 因此,如果原问题有解,该贪心方法一定能找到一种正确的方案。由 此可以证明,此贪心方法是正确的。确定贪心标准。

六、贪心的经典应用
(一) 、三个区间上的问题 1、选择不相交区间问题 2、区间选点问题 3、区间覆盖问题 (二) 、两个调度问题 1、流水作业调度问题 2、带限期和罚款的单位时间任务调度 (三)Huffman 编码 (四)最优合并问题 (一) 、三个区间上的问题 例题 2.3.3.6.1:给定 n 个开区间(ai, bi),选择尽量多个区间,使得这 些区间两两没有公共点。 【算法实现】首先按照 b1<=b2<=…<=bn 的顺序排序,依次考虑各个 活动,如果没有和已经选择的活动冲突,就选;否则就不选。 贪心策略:取满足条件的第一个区间;
第 14 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

【正确性】 如果不选 b1, 假设第一个选择的是 bi, 则如果 bi 和 b1 不交叉则多选 一个 b1 更划算;如果交叉则把 bi 换成 b1 不影响后续选择。 【样例输入】 6 34 67 13 25 56 47 【样例输出】4 按照 b[i]从小到大排序后的结果为: 13 34 25 56 47 67 选择的区间为: 13 34
第 15 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

56 67 思考:活动安排 设有 n 个活动,每个活动都要求使用同一资源,如演讲会场等,而在 同一时间内只有一个活动能使用这一资源。每个活动 i 都有一个要求 使用该资源的起始时间 si 和一个结束时间 fi,且 si<fi。如果选择了活 动 i,则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj) 不相交,则称活动 i 与活动 j 是相容的。也就是说,当 fi>=sj 或 fj>=si 时, 活动 i 与活动 j 相容。 选择出由互相兼容的活动组成的最大集合。 2、区间选点问题 例题 2.3.3.6.2:给定 n 个闭区间[ai, bi],在数轴上选尽量少的点,使 得每个区间内都至少有两个不同点(不同区间内含的点可以是同一 个) 。 【算法】 :先按照所有区间的结束位置从小到大排序。从区间 1 到区 间 n 进行循环,对于当前区间,若已选中的数不能覆盖它,则从区间 末尾向前扫描,若当前数未选中出现,则将该数标记为已选中,直至 使选中的数能满足该区间要求为止。

【样例输入】 4
第 16 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

36 24 02 47 【样例输出】4 【分析】{0,1,2};{2,3,4};{3,4,5,6};{4,5,6,7} [];[2];[2,1];[2,1,4];[2,1,4,6] 上述算法的指导思想是在某一区间中排列越靠后的数对以后区间的 影响越大, 即它在以后区间出现的可能性越大, 但未经严格数学证明。 例题 2.3.3.6.3:种树(NOIP 模拟试题) 一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路 边的地区被分割成块,并被编号为 1..n。每个块大小为一个单位尺寸 并最多可种一棵树。 每个居民想在门前种些树并指定了三个号码 b,e,t。 这三个数表示该居民想在 b 和 e 之间最少种 t 棵树。当然 b<=e,居民 必须保证在指定地区不能种多于地区被分割成块数的树,即要求 t<=e-b+1。允许居民想种树的各自区域可以交叉。出于资金短缺的原 因,环保部门请你求出能够满足所有居民的要求,需要种树的最少数量。 样例输入: 9 4 142 462
第 17 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

892 352 样例输出: 5 分析 方法 1:贪心策略 方法 2:利用差分约束系统解决 方法 3:使用树状数组 3、区间覆盖问题 给 n 个闭区间[ai,bi],选择尽量少的区间覆盖一条指定线段[s,t]。 本题的突破口仍然是区间包含和排序扫描, 不过先要进行一次预处理。 每个区间在[s,t]外的部分都应该预先被切掉,因为它们的存在是毫无 意义的。 在预处理后, 在相互包含的情况下, 小区间显然不应该考虑。 把各区间按照 a 从小到大排序,若 a 相同,则 b 从大到小排序(自动 处理掉区间包含) 。注 意:若区间 1 的起点大 于 s, 则无解 (因为其他 区间的起点更大,不可 能覆盖到 s 点) ,否则选择起点在 s 的最长区间[ai,bi]后,新的起点应 该设置为 bi, 并且忽略所有区间在 bi 之前的部分, 就像预处理一样。 虽然贪心策略比上题复杂,但是仍然只需要一次扫描,如下图,s 为 当前有效起点(此前部分已被覆盖) ,则应该选择区间 2。
第 18 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

贪心思想:在某个时刻 s,找一个满足 a[i]>=s 的 b[i]的最大值即可。 思考:区间(SDOI2005) 现给定 n 个闭区间[ai,bi],1<=i<=n。这些区间的并可以表示为一些不 相交的闭区间的并。 你的任务就是在这些表示方式中找出包含最少区 间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间 [a, b]和[c, d]是按照升序排列的,那么我们有 a<b<=c<=d。 任务:读入这些区间,计算满足给定条件的不相交闭区间,并把这些 区间按照升序输出。 思考:喷水装置 有一块草坪,长为 L,宽为 w;在它的中心线上装有 n 个点状的喷水 装置, 效果是让以它为中心半径为 ri 的圆被润湿, 选择尽量少的喷水 装置把整个草坪全部润湿。

1、

流水作业调度问题

第 19 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

【样例输入】 5 45873 62149 //作业个数 //每个作业 M1 机器上加工时间 //每个作业 M2 机器上加工时间

2、

带限期和罚款的单位时间任务调度

【样例输入】 7 2414643
第 20 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

60 50 30 20 10 70 40 排序后为: 4243146 70 60 50 40 30 20 10 分析 要使罚款最少,我们显然应尽量完成 w[i]值较大的工作。 此时,我们可以将工作按 w[i]从大到小进行排序,然后按照排好的 顺序依次对工作进行安排,安排的规则为:使处理工作 i 的时间既在 d[i]之内,又尽量靠后;如果 d[i]之内的时间都已经排满,就放弃处理 此项工作。 证明: 假设按照上述方法得到的解不是最优的,那么必然存在某个工作 j 应 当安排到处理的过程中,却没有得到安排。假设我们要将该工作安排 进去,由于时间 d[j]内都已经排满,就必然需要将一个已安排的工作 k 与之替换, 而 w[k]>=w[j], 这样替换显然会增加罚款的数额。 因此, 除上述安排方法以外的安排方法都不会使罚款的数额减少, 可得上述 方法得到的结果是最优的。

七、贪心方法的推广
贪心与其它算法结合 搜索的最优化剪枝( 生日蛋糕) 优化动态规划( Peter 的快餐店)
第 21 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

贪心方法与解题策略 最优方法不一定是最好方法 想不到最优解法就用较优解法

贪心与其它算法结合 例题 2.3.3.7.1:Peter 的快餐店(贪心与动态规划) 【问题描述】Peter 最近在 R 市新开了一家快餐店。 该快餐店准备推 出一种套餐,每套由 A 个汉堡、B 个薯条和 C 个饮料组成。为了提高 产量,Peter 引进了 N 条生产线。所有生产线都可以生产汉堡、薯条 和饮料,由于每条生产线一天能工作的时间是有限的、不同的,而汉 堡、薯条和饮料的单位生产时间又不同,Peter 需要知道,怎样安排 才能是一天中生产的套餐量最大。假设一天中汉堡、薯条和饮料的产 量均不超过 100 个,且生产线总数小于等于 10。 【文件输入】 输入文件有四行。 第一行为三个不超过 100 的正整数 A、B、C。 第二行为三个不超过 100 的正整数 P1、P2、P3,分别为汉堡、薯 条和饮料的单位生产耗时。 第三行为 N(0<=N<=10) 第四行为 N 个不超过 10000 的正整数,分别为各条生产线每天 所提供的生产时间。 【文件输出】输出文件仅一行,即每天套餐的最大产量。
第 22 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

分析 本题是一个非常典型的资源分配问题。 由于每条生产线的生产是相互 独立, 不互相影响的, 所以此题可以以生产线为阶段用动态规划求解。 状态表示: 用 p[i][j][k]表示前 i 条生产线生产 j 个汉堡,k 个薯条的 情况下最多可生产饮料的个数。 用 r[i][j][k]表示第 i 条生产线生产 j 个汉堡,k 个薯条的情况下最多可 生产饮料的个数。 状态转移方程 :p[i][j][k]=Max{p[i-1][j1][k1]+r[i][j-j1][k-k1]} (0<=j1<=j,0<=k1<=k, 且(j-j1)*p1+(k-k1)*p2<= 第 i 条生产线的生产时间) 但这样的算法是非常粗糙的,稍加分析可以发现,此算法的时间复杂 度为 N*1004,当 N=10 的时候, 时间复杂度将达到 10*1004=109, 这是 根本无法承受的。 用贪心方法作预处理 : 首先计算出一天生产套数的上限值:min{100 div A,100 div B,100 div C} 接着, 用贪心方法计算出这 N 条生产线可以生产的套数, 并与上限比 较,大于或等于则输出上限值并退出,否则再调用动态规划。因为贪 心方法的代价很低, 这里甚至可以使用多次贪心标准不同的贪心方法, 取其最大值。 在运行动态规划的过程中, 也可以每完成一阶段工作便与上限值进行 比较,将贪心思想充分融入到动态规划过程中,这样以来,便可望在 动态规划完成前提前结束程序。

第 23 页 ,共 24 页

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十讲

算法步骤:

贪心小结: 贪心作为一种解题思路,虽然有时无法证明它的正确性,但在无法找 到其他算法的时候,不失为一种好方法。 并且,贪心与其他算法的结合,可以对其他算法起到优化作用。

第 24 页 ,共 24 页


相关文章:
pascal算法合集
pascal算法合集_学科竞赛_高中教育_教育专区。pascal语言编写手打整理 NOIP free ...(true); end; 10.第 n 最短路径问题 *第二最短路径:每举最短路径上的...
pascal 基本算法
Pascal算法中基本排序算... 10页 1下载券 Pascal基本算法及数据结... 26页 ...{将第 i 个元素向下筛} var j,x:longint; begin j:=i*2;x:=a[i];...
PASCAL算法合集
PASCAL算法合集_韩语学习_外语学习_教育专区。PASCAL算法合集 基本算法模块 一、数论算法 1.求两数的最大公约数 function gcd(a,b:integer):integer; begin if ...
Pascal算法
Pascal算法_计算机软件及应用_IT/计算机_专业资料。算法: 算法是程序的基础。有了一个好的算法,再进行编码,把 算法转换成任何一个程序设计语言所表示的程序。算法...
第十讲repeat
第十讲repeat_计算机软件及应用_IT/计算机_专业资料pascal 第10 讲——repeat 循环【例 1】 从键盘输入一个整数 x (x<=10000) ,若 x 的各位数字之和为 ...
PASCAL讲义
注意掌握算法,做到举一反三,一通百通; 3、 认真完成...pascal 中表示实型常量的形式有两种。 ⑴十进制表示...Pascal暑假精英班讲义 第... 2页 免费 统计楼梯阶...
pascal-基本算法模块
pascal-基本算法模块_计算机软件及应用_IT/计算机_专业资料。基本算法模块 For ...(temp); end; 十进制转 k 进制: procedure change_to_k(num:bignum;k:...
pascal入门算法.doc
pascal 三角”) [杨辉三角形]:打印杨辉三角形的前10行,杨辉三角形如图: ...中学算法艺术 边界条件 n=1 f(1)=1 n=2 f(2)=2 n n-2 种排 从第...
pascal常用算法
百度文库 专业资料 IT/计算机 计算机软件及应用上传文档支持以下设备:扫二维码下载...PASCAL算法 30页 2财富值 pascal 算法 8页 10财富值 pascal基本算法小全 8页...
pascal算法-比赛2
pascal算法-比赛2_计算机软件及应用_IT/计算机_专业资料。第3章 算法与程序设计...样例输入:2 2 10 样例输出:1414213652 注意:口令的最后一位请使用去尾法保留,...
更多相关标签:
麻省理工算法导论讲义 | mit 算法导论 讲义 | 秦九韶算法讲义 | 数据结构与算法讲义 | 贪心算法 pascal | pascal算法 | spfa算法pascal | dijkstra算法pascal |