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

admin2010-01-15 57

问题请将图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://www.kaotiyun.com/show/DcDZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

某公司采用的软件开发过程通过了CMM2认证，表明该公司(30)。

数据库系统通常采用三级模式结构：外模式、模式和内模式。这三级模式分别对应数据库的__________。

关于软件著作权产生的时间，下面表述正确的是(10)。

软件测试按实施组织分，测试应该包括以下的(50)。①开发方测试②用户方测试③第三方测试④验收测试⑤确认测试

编译和解释是实现高级程序设计语言的两种方式，其区别主要在于______。

注册会计师通常先确定一个基准，再乘以某一百分比作为财务报表整体的重要性。下列因素中，注册会计师在确定百分比时不需要考虑的是()。

甲租用乙的一套住房，搬进去以后发现房屋漏雨严重。则()。

Everyoneknowsthatthefirstruleofdrivingisnevertakingyoureyesofftheroad.Teendrivers【C1】________beingcareful,bu

下列各组中现在是但历史上不是异体字的一组是()

雷诺现象或雷诺病发病的病理生理机制为

在合同支付项目中，业主先支付给承包人，并在一定期间又要扣回的款项有()。

需胆盐激活的消化酶是和。

钟某借口要买烟，向店主提出要查看香烟，趁店主不注意就用假烟与店主真烟调换，钟某采取类似办法共获取价值8000元的香烟。钟某的行为构成（）罪。

有许多美丽的人并不善良，但没有一个善良的人是不美丽的。以下不能从上述论断中推出的是：

AlltherecentnewsonAIDSisbad.ThedeathofRockHudson【C1】publicconcernaboutthe【C2】almosttothepointofp

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

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

软考中级

某公司采用的软件开发过程通过了CMM2认证，表明该公司(30)。

数据库系统通常采用三级模式结构：外模式、模式和内模式。这三级模式分别对应数据库的__________。

关于软件著作权产生的时间，下面表述正确的是(10)。

软件测试按实施组织分，测试应该包括以下的(50)。①开发方测试②用户方测试③第三方测试④验收测试⑤确认测试

编译和解释是实现高级程序设计语言的两种方式，其区别主要在于______。

注册会计师通常先确定一个基准，再乘以某一百分比作为财务报表整体的重要性。下列因素中，注册会计师在确定百分比时不需要考虑的是()。

甲租用乙的一套住房，搬进去以后发现房屋漏雨严重。则()。

Everyoneknowsthatthefirstruleofdrivingisnevertakingyoureyesofftheroad.Teendrivers【C1】________beingcareful,bu

下列各组中现在是但历史上不是异体字的一组是()

雷诺现象或雷诺病发病的病理生理机制为

在合同支付项目中，业主先支付给承包人，并在一定期间又要扣回的款项有()。

需胆盐激活的消化酶是________和________。

钟某借口要买烟，向店主提出要查看香烟，趁店主不注意就用假烟与店主真烟调换，钟某采取类似办法共获取价值8000元的香烟。钟某的行为构成（）罪。

有许多美丽的人并不善良，但没有一个善良的人是不美丽的。以下不能从上述论断中推出的是：

AlltherecentnewsonAIDSisbad.ThedeathofRockHudson【C1】______publicconcernaboutthe【C2】______almosttothepointofp

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

需胆盐激活的消化酶是和。

AlltherecentnewsonAIDSisbad.ThedeathofRockHudson【C1】publicconcernaboutthe【C2】almosttothepointofp