首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
请将图3-25中的(1)~(3)空缺处的内容填写完整。 对于本试题的作业处理问题,用图3-25的贪心算法能否求得最高收益? (6)。(能或不能) 用贪心算法求解任意给定问题时,是否一定能得到最优解? (7)。(能或不能)
请将图3-25中的(1)~(3)空缺处的内容填写完整。 对于本试题的作业处理问题,用图3-25的贪心算法能否求得最高收益? (6)。(能或不能) 用贪心算法求解任意给定问题时,是否一定能得到最优解? (7)。(能或不能)
admin
2010-01-15
27
问题
请将图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://jikaoti.com/ti/iQi7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在面向对象技术中,(43)是一组具有相同结构、相同服务、共同关系和共同语义的(44)集合,其定义包括名称、属性和操作。(44)
假设磁盘块与缓冲区大小相同,每个盘块读入缓冲区的时间为10μs,由缓冲区送至用户区的时间是5μs,系统对每个磁盘块数据的处理时间为2μs。若用户需要将大小为10个磁盘块的Docl文件逐块从磁盘读入缓冲区,并送至用户区进行处理,那么采用单缓冲区需要花费的时间
某企业研发信息系统的过程中,______不属于数据库管理员(DBA)的职责。
以下各项中,(47)属于安装测试应关注的内容。①安装手册的评估②安装选项和设置的测试③安装顺序测试④修复安装测试与卸载测试
给定包含n个正整数的数组A和正整数x,要判断数组A中是否存在两个元素之和等于x。先用插入排序算法对数组A进行排序,再用以下过程P来判断是否存在两个元素之和等于x。low=l;high=n;while(high>low)ifA[low]+A[hig
在结构化分析方法中,用于行为建模的模型是①,其要素包括②。①处应填入?
以下不属于单元测试测试内容的是______。
行为型设计模式描述类或对象如何交互和如何分配职责。______模式是行为型设计模式。
系统交付后,修改偶尔会出现乱码的问题,该行为属于________________维护。
网络测试类型包括________。①网络可靠性测试②网络可接受性测试③网络瓶颈测试④网络容量规划测试
随机试题
QC小组是按PDCA循环进行活动的,P是指计划,D是实施,C是检查,A是()。
在TCP/IP协议体系结构中,IP首部包括32比特长的源地址和( )地址。
一个民族进步的灵魂是
急性肾衰竭少尿期危害最大的电解质改变是
甲状腺大部切除术后发生甲状腺危象的原因是()
下列对于王某遗产的说法哪些是正确的?()若王某之子甲在王某去世之后、遗产分配之前死亡,下列说法哪个是正确的?()
某新建生产型项目,采用主要车间系数法进行固定资产投资估算,经估算主要生产车间的投资为2800万元,辅助及公用系统投资系数为0.67,行政及生活福利设施投资系数为0.25,其他投资系数为0.38,则该项目的投资额为()万元。
甲、乙两列火车同时从相距600千米的A、B两地同时出发,相向而行,中途相遇后甲火车又经过1小时到达B地,乙火车又经过4小时才到达A地,那么当甲火车行驶100千米时乙火车行驶的距离为()千米。
下列说法不正确的是:
Evenbeforetheopeningceremony,arecordhadbeenbrokenatSochi:12newevents,themostforanyOlympics,werescheduledto
最新回复
(
0
)