早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->
对于本试题的作业处理问题,用图3-25的贪心算法能否求得最高收益?(6)。(能或不能) 用贪心算法求解
题目
对于本试题的作业处理问题,用图3-25的贪心算法能否求得最高收益? (6)。(能或不能)
用贪心算法求解任意给定问题时,是否一定能得到最优解? (7)。(能或不能)
参考答案
正确答案:
这是一道判断贪心算法是否能求得最优解的应用分析题。对于本试题的作业处理问题,用图3-25的贪心算法策略,能求得最优解(即能求得最高收益)。但不是所有的问题都能通过贪心策略来求得最优解,一个典型的例子是0—1背包问题。例如,有3件物品,背包可容纳50磅重的东西,每件物品的详细信息如表3-14所示,问如何装包使得其价值最大? 如果按贪心策略求解该问题,优先选择单位价值最大的物品,则先选择物品R,然后选择物品S。由于此时背包容量还剩下50-10-20=20,不足以容纳物品T,故总价值为60+100=160美元。但若选择物品 S和物品T,容量总和为20+30,小于等于总容量50,得到总价值为100+120=220美元,会得到更优解。此时用贪心策略不能得到最优解。
这是一道判断贪心算法是否能求得最优解的应用分析题。对于本试题的作业处理问题,用图3-25的贪心算法策略,能求得最优解(即能求得最高收益)。但不是所有的问题都能通过贪心策略来求得最优解,一个典型的例子是0—1背包问题。例如,有3件物品,背包可容纳50磅重的东西,每件物品的详细信息如表3-14所示,问如何装包使得其价值最大? 如果按贪心策略求解该问题,优先选择单位价值最大的物品,则先选择物品R,然后选择物品S。由于此时背包容量还剩下50-10-20=20,不足以容纳物品T,故总价值为60+100=160美元。但若选择物品 S和物品T,容量总和为20+30,小于等于总容量50,得到总价值为100+120=220美元,会得到更优解。此时用贪心策略不能得到最优解。
看了对于本试题的作业处理问题,用图...的网友还看了以下:
CAD比例换算图的比例为1:150.那个图中的1550的实际距离是多少 数学 2020-04-06 …
cad图纸按1比50写的 想算实际的面积怎么算我想算这个图的实际面具 ,怎么算,要详细,下面这个是 数学 2020-04-06 …
贪吃中的贪是什么意思 语文 2020-04-07 …
起早贪黑中的贪是动词吗 语文 2020-04-07 …
美国有位历史学家说:“凡尔赛和约的制定者……是在恨、贪、惧的气氛中集合于巴黎的。”他们贪婪和恐惧的 历史 2020-04-07 …
图形计算:一个圆柱沿直径竖直切开得到图形,请计算图的表面积和体积. 数学 2020-04-09 …
我以不贪为宝的贪什么意思 语文 2020-05-22 …
关于计算机的判断题1、计算机病毒主要以存储介质和计算机网络为媒介进行传播.2、世界上第一台计算机的 其他 2020-05-23 …
对犯贪污罪的,个人贪污数额在五万元以上不满十万元的,处()年以上有期徒刑,可以并处没收财产;情节 职业技能鉴定 2020-05-27 …
图图的计算器上6这个键坏了.他在计算76x9999时,可以怎样按键计算? 数学 2020-06-04 …