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

admin2010-01-15 34

问题请将图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)。(能或不能)

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

软考中级

软件测试的对象不包括()。

当用户需求不清晰、需求经常发生变化、系统规模不太大时，最适宜采用的软件开发方法是__________。

标准符合性测试中的标准分类包括______。①数据内容类标准②通信协议类标准③开发接口类标准④信息编码类标准

行为型设计模式描述类或对象如何交互和如何分配职责。______模式是行为型设计模式。

某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续时间(天)，则完成该项目的最少时间为天。活动FG的松弛时间为天。

我国历史上最早从理论上剖析方剂的医家是()(1997年第41题)

Often,earlyonafinesummermorning,thegrassiswetwith______.

60钴治疗机控制台指示灯提示为照射中的是

联合国救灾协调员办事处在美国市场采购原产于加拿大的冰雪救灾物资无偿援助我国，该批物资在洛杉矶装船，在日本东京中转后运抵我国。这种情况其报关单“起运国(地区)”栏目应填为()。

基金监管的基本原则不包括()。

小组工作准备阶段，确定小组工作能够解决的问题及其具体范围的是()。

幼儿园教育评价根据评价的功能和运行时间分为()。

项目管理器的“文档”选项卡用于显示和管理

ProblemsoftheElderlyGerontologists(老年人问题学者)studyhowoldpeoplearetreatedwithinasocietyandhowtheelderlydeal

Alicesoldherhair______tenyuan.

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

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

软考中级

软件测试的对象不包括()。

当用户需求不清晰、需求经常发生变化、系统规模不太大时，最适宜采用的软件开发方法是__________。

标准符合性测试中的标准分类包括______。①数据内容类标准②通信协议类标准③开发接口类标准④信息编码类标准

行为型设计模式描述类或对象如何交互和如何分配职责。______模式是行为型设计模式。

某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续时间(天)，则完成该项目的最少时间为________________天。活动FG的松弛时间为________________天。

我国历史上最早从理论上剖析方剂的医家是()(1997年第41题)

Often,earlyonafinesummermorning,thegrassiswetwith______.

60钴治疗机控制台指示灯提示为照射中的是

联合国救灾协调员办事处在美国市场采购原产于加拿大的冰雪救灾物资无偿援助我国，该批物资在洛杉矶装船，在日本东京中转后运抵我国。这种情况其报关单“起运国(地区)”栏目应填为()。

基金监管的基本原则不包括()。

小组工作准备阶段，确定小组工作能够解决的问题及其具体范围的是()。

幼儿园教育评价根据评价的功能和运行时间分为()。

项目管理器的“文档”选项卡用于显示和管理

ProblemsoftheElderlyGerontologists(老年人问题学者)studyhowoldpeoplearetreatedwithinasocietyandhowtheelderlydeal

Alicesoldherhair______tenyuan.

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

某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续时间(天)，则完成该项目的最少时间为天。活动FG的松弛时间为天。