请将图3-25中的(1)～(3)空缺处的内容填写完整。对于本试题的作业处理问题，用图3-25的贪心算法能否求得最高收益? (6)。(能或不能) 用贪心算法求解任意给定问题时，是否一定能得到最优解? (7)。(能或不能)

admin2010-01-15 47

问题请将图3-25中的(1)～(3)空缺处的内容填写完整。
对于本试题的作业处理问题，用图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美元，会得到更优解。此时用贪心策略不能得到最优解。

解析

转载请注明原文地址:https://kaotiyun.com/show/DcDZ777K

本试题收录于：软件设计师下午应用技术考试题库软考中级分类

软件设计师下午应用技术考试

软考中级

相关试题推荐

随机试题

最新回复(0)

请将图3-25中的(1)～(3)空缺处的内容填写完整。对于本试题的作业处理问题，用图3-25的贪心算法能否求得最高收益? (6)。(能或不能) 用贪心算法求解任意给定问题时，是否一定能得到最优解? (7)。(能或不能)

软件设计师下午应用技术考试

软考中级

将高级语言程序翻译为机器语言程序的过程中，常引入中间代码，其好处是()。

编译器和解释器是两种基本的高级语言处理程序。编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等阶段，其中，___________并不是每个编译器都必需的。

集线器与网桥的区别是__________。

软件工程概念的提出是由于______。A．计算技术的发展B．软件危机的出现C．程序设计方法学的影响D．其他工程科学的影响

下图是一个软件项目的活动图，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的值表示完成活动所需要的时间，则关键路径长度为______。

修改现有软件系统的设计文档和代码以增强可读性，这种行为属于________维护。

对于逻辑表达式(((a＞0)&&(b＞0))‖c＜5)，需要______个测试用例才能完成条件组合覆盖。

与XY(即X与Y不相同时，XY的结果为真)等价的逻辑表达式为________________。

某行业中A、B两家公司为上市公司，2012年有关资料如下：(1)2012年1月1日，A公司发行在外普通股数量为82000万股，所得税率为15％；(2)2012年1月1日，A公司在2010年1月1日发行的2．2亿元可转换债券可以以每股11元的价格转换成公

关于标准审计报告表述正确的是（）

下列哪一项不属于灭菌法

与质量管理目标无关的是

患者烦渴多饮，口干舌燥，兼见小便频多，舌边尖红苔薄黄，脉洪数。其治法是

患儿男，生后2天，出生体重为2400g。因吸入性肺炎入院，入院时患儿呼吸急促，口唇稍发绀。即置于辐射保暖床上抢救。为该患儿选择的给氧方法是

施工图预算审查方法中，审查质量高、效果好但工作量大的是(　　)。

下列属于公司债券上市交易公司发布临时报告的重大事件的有()。

在直三棱柱ABC—A1B1C1中，AB=1，AC=AA1=，∠ABC=60°。证明：AB⊥A1C；

Atatimewhentheworldisshortofcausesforcelebration,hereisacandidate:withinthenextfewmonthswomenwillcrossth

请将图3-25中的(1)～(3)空缺处的内容填写完整。 对于本试题的作业处理问题，用图3-25的贪心算法能否求得最高收益? (6)。(能或不能) 用贪心算法求解任意给定问题时，是否一定能得到最优解? (7)。(能或不能)

软件设计师下午应用技术考试

软考中级

将高级语言程序翻译为机器语言程序的过程中，常引入中间代码，其好处是()。

编译器和解释器是两种基本的高级语言处理程序。编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等阶段，其中，___________并不是每个编译器都必需的。

集线器与网桥的区别是__________。

软件工程概念的提出是由于______。A．计算技术的发展B．软件危机的出现C．程序设计方法学的影响D．其他工程科学的影响

下图是一个软件项目的活动图，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的值表示完成活动所需要的时间，则关键路径长度为______。

修改现有软件系统的设计文档和代码以增强可读性，这种行为属于________维护。

对于逻辑表达式(((a＞0)&&(b＞0))‖c＜5)，需要______个测试用例才能完成条件组合覆盖。

与XY(即X与Y不相同时，XY的结果为真)等价的逻辑表达式为________________。

某行业中A、B两家公司为上市公司，2012年有关资料如下：(1)2012年1月1日，A公司发行在外普通股数量为82000万股，所得税率为15％；(2)2012年1月1日，A公司在2010年1月1日发行的2．2亿元可转换债券可以以每股11元的价格转换成公

关于标准审计报告表述正确的是（）

下列哪一项不属于灭菌法

与质量管理目标无关的是

患者烦渴多饮，口干舌燥，兼见小便频多，舌边尖红苔薄黄，脉洪数。其治法是

患儿男，生后2天，出生体重为2400g。因吸入性肺炎入院，入院时患儿呼吸急促，口唇稍发绀。即置于辐射保暖床上抢救。为该患儿选择的给氧方法是

施工图预算审查方法中，审查质量高、效果好但工作量大的是( )。

下列属于公司债券上市交易公司发布临时报告的重大事件的有()。

在直三棱柱ABC—A1B1C1中，AB=1，AC=AA1=，∠ABC=60°。证明：AB⊥A1C；

Atatimewhentheworldisshortofcausesforcelebration,hereisacandidate:withinthenextfewmonthswomenwillcrossth

请将图3-25中的(1)～(3)空缺处的内容填写完整。对于本试题的作业处理问题，用图3-25的贪心算法能否求得最高收益? (6)。(能或不能) 用贪心算法求解任意给定问题时，是否一定能得到最优解? (7)。(能或不能)

施工图预算审查方法中，审查质量高、效果好但工作量大的是(　　)。