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

admin2010-01-15 49

问题请将图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[1．．10，1．．8]中的元素按行存放，每个元素占用4个存储单元，已知第一个数组元素a[1，1]的地址为1004，那么a[5,6]的地址为________________。

在一个完整的功能测试过程中，______不属于应该编写的测试文档。A．测试需求文档B．测试用例文档C．测试标准D．问题报告单

以下图片中，表示功率表的是()。

Thegardenerwascalledintotelltheway______thepoordoghaddied.

某工业项目，与一级声环境评价范围相比，二级、三级可根据下列哪些情况适当缩小评价范围?()

以下不属于非电离辐射的是（）。

在会计工作交接中，接替会计人员在交接时因疏忽没有发现所接收的会计资料在真实性，完整性方面存在问题，如果事后在这一方面发现的问题，那么则应由接替会计人员承担相应的法律责任。()

试述蒙台梭利教育思想、教育内容及其教育方法。

小明今年5岁半，当老师问小明“为什么把积木扔进水里，积木会浮起来"时，小明回答“因为积木是由木头做的，而木头沉不下去"。由此可以推断出小明的()开始萌芽。

在成本控制过程中，对项目方案进行技术经济分析，只有采用综合评价而优选的项目方案才能算是最佳方案。对最佳方案的要求是技术上最佳、经济上_________。

一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是()。

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

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

软考中级

对现有软件系统中一些数据处理的算法进行改进，以提高效率，从而更快地响应用户的服务要求。这种行为属于____________维护。

传统编译器进行词法分析、语法分析、代码生成等步骤的处理时，前一阶段处理的输出是后一阶段处理的输入，则采用的软件体系结构风格是①。该体系结构的优点不包括②。①处应填入？

在结构化分析方法中，用于行为建模的模型是①，其要素包括②。①处应填入？

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

设数组a[1．．10，1．．8]中的元素按行存放，每个元素占用4个存储单元，已知第一个数组元素a[1，1]的地址为1004，那么a[5,6]的地址为________________。

在一个完整的功能测试过程中，______不属于应该编写的测试文档。A．测试需求文档B．测试用例文档C．测试标准D．问题报告单

以下图片中，表示功率表的是()。

Thegardenerwascalledintotelltheway______thepoordoghaddied.

某工业项目，与一级声环境评价范围相比，二级、三级可根据下列哪些情况适当缩小评价范围?()

以下不属于非电离辐射的是（）。

在会计工作交接中，接替会计人员在交接时因疏忽没有发现所接收的会计资料在真实性，完整性方面存在问题，如果事后在这一方面发现的问题，那么则应由接替会计人员承担相应的法律责任。()

试述蒙台梭利教育思想、教育内容及其教育方法。

小明今年5岁半，当老师问小明“为什么把积木扔进水里，积木会浮起来"时，小明回答“因为积木是由木头做的，而木头沉不下去"。由此可以推断出小明的()开始萌芽。

在成本控制过程中，对项目方案进行技术经济分析，只有采用综合评价而优选的项目方案才能算是最佳方案。对最佳方案的要求是技术上最佳、经济上_________。

一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是()。

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