首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
请填充图4-1中的空缺(1)、(2)和(3)处。 对于本题的作业处理问题,用图4-1的贪心算法策略,能否求得最高收益?(6)。用贪心算法求解任意给定问题时,是否一定能得到最优解?(7)。
请填充图4-1中的空缺(1)、(2)和(3)处。 对于本题的作业处理问题,用图4-1的贪心算法策略,能否求得最高收益?(6)。用贪心算法求解任意给定问题时,是否一定能得到最优解?(7)。
admin
2008-11-02
64
问题
请填充图4-1中的空缺(1)、(2)和(3)处。
对于本题的作业处理问题,用图4-1的贪心算法策略,能否求得最高收益?(6)。用贪心算法求解任意给定问题时,是否一定能得到最优解?(7)。
选项
答案
(6)能,或可以、行及其他含义相同的词语 (7)不能,或不可以、不行及其他含义相同的词语
解析
本题考查的是算法的设计和分析技术。
问题1考查的是贪心算法的流程图。第(1)空表示第2个作业到第n个作业的主循环,i是循环控制变量,故第(1)空填入i<=n。
应注意到数组/中的作业J
(1≤i≤k)是在其期限之前完成的作业,且d[J
]≤d[J[i+1]] (1≤id
。另一方面, J[D[R]]与r的关系只有两种:J[d[r]]>r,表示还可能在J[1]与J[r]之间插入作业i;J[d[r]]=r,表示不可能在J[1]~J[r]之间插入作业i。J[d[r]] 问题2是本题算法的一个实例。6个作业的收益已经按降序排好序。根据流程图,将作业1,2,4和5放入数组J中,并得到总收益为220,具体过程如表4-1所示。
问题3考查算法策略。对于该题,贪心策略可以求得最优解。但不是所有的问题都能通过贪心策略来求得最优解,一个典型的例子是0-1背包问题。举例如下,有三件物品,背包可容纳50磅重的东西,每件物品的详细信息如表4-2所示,问如何装包使得其价值最大?
如果按贪心策略求解该问题,优先选择单位价值最大的物品,则先选择物品1,然后选择物品2。由于此时背包容量还剩下50-10-20=20,不足以容纳物品3,故总价值为 60+100=160美元。但若选择物品2和物品3,容量总和为20+30,小于等于总容量50,得到总价值为100+120=220,会得到更优解。此时用贪心策略不能得到最优解。
转载请注明原文地址:https://kaotiyun.com/show/n5DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
用等价类法划分Windows文件名称,应该分成(39)—个等价区间。
风险分析在软件项目开发中具有重要作用,包括风险识别、风险预测、风险评估和风险控制等。“建立风险条目检查表”是(18)时的活动,“描述风险的结果”是(19)时的活动。
针对逻辑覆盖(53)叙述是不正确的。
为验证某音乐会订票系统是否能够承受大量用户同时访问,测试工程师一般采用(62)测试工具。
软件能力成熟度模型(CMM)将软件能力成熟度自低到高依次划分为5级。目前,达到CMM第3级(已定义级)是许多组织努力的目标,该级的核心是(29)。
下面关于软件测试模型的描述中,不正确的包括______。①V模型的软件测试策略既包括低层测试又包括高层测试,高层测试是为了源代码的正确性,低层测试是为了使整个系统满足用户的需求②V模型存在一定的局限性,它仅仅把测试过程作为在需求分析、概要设
某指令流水线由4段组成,各段所需要的时间如下图所示。连续输入8条指令时的吞吐率(单位时间内流水线所完成的任务数或输出的结果数)为()。
函数f()、g()的定义如下所示,已知调用f时传递给其形参x的值是10,若以传值方式调用g,则函数f的返回值为__________。
将图2-1中(1)和(2)空缺名称填写在应的位置。ADSL有哪两种IP地址的分配方式?
随机试题
切片可以通过以下哪些方式来制作:
师陀的《果园城记》是()
生活史中不需要中间宿主的是
某建筑物采用TN—C—S系统供电,建筑物地下室设有与大地绝缘的防水层,PEN线进户后即分为PE线和N线,并用人工接地极将PE线重复接地,变电所系统接地RA和建筑物重复接地RB阻值分别为4Ω及10Ω,各段线路的电阻值如下图所示,为简化计算可忽略工频条件下的回
【背景资料】某变压器厂装配车间为全钢结构厂房,跨度为28m,长180m,轨道中心跨距为22m,轨道顶标高22.5m。某安装公司承接了一台160/40t桥式起重机安装工程,起重机自重175.8t,安装工期15d。为了确定能保证安全可靠、保证工期、降低
165,140,124,(),111
已知关键字序列5,8,12,19,28,20,15,22是小根堆(最小堆),插入关键字3,调整后得到的小根堆是_______。
判断一组数据是否适合做因素分析可以做以下哪些检验?()
数据字典(DD)所定义的对象都包含于
Aseriesofseminars______scheduled.
最新回复
(
0
)