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

admin2010-01-15 20

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

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

软考中级

ICMP协议属于因特网中的(27)协议，ICMP协议数据单元封装在(28)中传送。(28)

为检验某Web系统并发用户数是否满足性能要求，应进行()。

(42)不是文档测试包括的内容。

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

一个Web信息系统所需要进行的测试包括____________。①功能测试②性能测试③可用性测试④客户端兼容性测试⑤安全性测试

下面为C语言程序，边界值问题可以定位在(45)。　　　　int　data(3),　　　　int　i,　　　　for(i=1,　i＜=3,　i++)data(i)=100

适用于现场调查的维生素A营养状况评价方法是

工程材料按化学成分分类包括(　　)。

高桩码头工程施工组织设计编制中，“工程项目主要情况”包括工程名称、建设地点、建设规模、总工期、()、主要工程量、分包队伍选择、新技术、新材料应用等。

党的作风建设的核心问题是()。

把下面的六个图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是：

简述国外当代课程改革的主要特点。

求微分方程y’’-y’-6y=0的通解．

Whataretheydiscussingabout?

HowtoapproachListeningTestPartOne•InthispartoftheListeningTestyoulistentoamonologue,e.g.apresentation.•B

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

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

软考中级

ICMP协议属于因特网中的(27)协议，ICMP协议数据单元封装在(28)中传送。(28)

为检验某Web系统并发用户数是否满足性能要求，应进行()。

(42)不是文档测试包括的内容。

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

一个Web信息系统所需要进行的测试包括____________。①功能测试②性能测试③可用性测试④客户端兼容性测试⑤安全性测试

下面为C语言程序，边界值问题可以定位在(45)。 int data(3), int i, for(i=1, i＜=3, i++)data(i)=100

适用于现场调查的维生素A营养状况评价方法是

工程材料按化学成分分类包括( )。

高桩码头工程施工组织设计编制中，“工程项目主要情况”包括工程名称、建设地点、建设规模、总工期、()、主要工程量、分包队伍选择、新技术、新材料应用等。

党的作风建设的核心问题是()。

把下面的六个图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是：

简述国外当代课程改革的主要特点。

求微分方程y’’-y’-6y=0的通解．

Whataretheydiscussingabout?

HowtoapproachListeningTestPartOne•InthispartoftheListeningTestyoulistentoamonologue,e.g.apresentation.•B

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

下面为C语言程序，边界值问题可以定位在(45)。　　　　int　data(3),　　　　int　i,　　　　for(i=1,　i＜=3,　i++)data(i)=100

工程材料按化学成分分类包括(　　)。