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

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基本算法及数据结构
10.第 n 最短路径问题 *第二最短路径:每举最短路径上的每条边,每次删除一...18 回复此发言 7 Pascal 基本算法及数据结构 var i:integer; begin if dep=...
pascal入门算法.doc
7 2010 聿怀初级中学算法艺术 D厂的代表说:C厂的产品不是最好的。 E厂的...“pascal 三角”) [杨辉三角形]:打印杨辉三角形的前10行,杨辉三角形如图: ...
pascal-基本算法模块
pascal-基本算法模块_计算机软件及应用_IT/计算机_...基本算法模块中最重要的是基本程序框架,也就是说,...(temp); end; 十进制转 k 进制: procedure ...
pascal常用算法
PASCAL算法 30页 2财富值 pascal 算法 8页 10财富值 pascal基本算法小全 8页...{初始化定义 n 个集合,第 I 个集合包含一个元素 I} p:=n-1; q:=1; ...
pascal递归算法-noip竞赛材料
pascal递归算法-noip竞赛材料_学科竞赛_高中教育_教育...一般来说,能够用 信息学竞赛―――递归算法 一个...例 10、计算交点数 问题描述: 平面上有 n 条直线...
很全面的信息学奥赛_算法教程_Pascal
很全面的信息学奥赛_算法教程_Pascal 非常全面!非常全面!隐藏>> 信息学奥赛辅导教程第3章 算法与程序设计模块 3.1 算法 算法是对特定问题求解步骤的一种描述,它是...
Pascal教程(整理版)
67 第六章 程序设计与基本算法 ......10 38 308 -4951 63 ~1.1×104932 -2 +1~2 -1 8 在 Turbo Pascal 中实数的表示用科学记数法,可认为由三部分...
[教案]Pascal教程(整理版)
Pascal基础算法教案 81页 免费 pascal竞赛辅导教案 45页 5财富值 赵宗昌校本课程...10 第一节 条件语句与复合语句 ......
NOIP(pascal)典型算法题集
NOIP(pascal)典型算法设计题集 NOIP(pascal)典型算法设计题集 典型第一章 算法的初步第一节 程序设计与算法 一、算法 算法是解决问题方法的精确描述,但是并不是...
pascal教程
递归算法 第二节 回溯算法 第七章 数据结构及其应用 第一节 线性表 第二节 ...Pascal 还定义了五个标准实数类型,列表所示 Extended 1.9×10-4951~1.1×...
更多相关标签: