首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
请填充图4-1中的空缺(1)、(2)和(3)处。 对于本题的作业处理问题,用图4-1的贪心算法策略,能否求得最高收益?(6)。用贪心算法求解任意给定问题时,是否一定能得到最优解?(7)。
请填充图4-1中的空缺(1)、(2)和(3)处。 对于本题的作业处理问题,用图4-1的贪心算法策略,能否求得最高收益?(6)。用贪心算法求解任意给定问题时,是否一定能得到最优解?(7)。
admin
2008-11-02
69
问题
请填充图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
软件设计师下午应用技术考试
软考中级
相关试题推荐
设关系模式R(A,B,C),传递依赖指的是(16);下列结论错误的是(17)。
若关系R、S如下图所示,则R与S自然连接后的属性列数和元组个数分别为(28);π1,4(σ3=6(R×S))=(29)。
设有职工EMP(职工号,姓名,性别,部门号,职务,进单位时间,电话),职务JOB(职务,月薪)和部门DEPT(部门号,部门名称,部门电话,负责人)实体集。一个职务可以由多个职工担任,但一个职工只能担任一个职务,并属于一个部门,部门负责人是一个职工。下图所示
负载压力性能测试需求分析时,应该选择(63)类型的业务作为测试案例。 ①高吞吐量的业务 ②业务逻辑复杂的业务 ③高商业风险的业务 ④高服务器负载的业务 ⑤批处理的业务
利用高速通信网络将多台高性能工作站或微型机互连构成机群系统,其系统结构形式属于(5)计算机。
下列设备和技术中,(65)不属于数据安全策略范畴。
已知函数f()、g()的定义如下所示,执行表达式“x=f(5)”的运算时,若函数调用g(a)是引用调用(callbyreference)方式,则执行“x:f(5)”后x的值为(7);若函数调用g(a)是值调用(callbyvalue)方式,
结构化开发方法中,(35)主要包含对数据结构和算法的设计。对算法设计时,其主要依据来自(36)。描述算法时,(37)不是理想的表达方式。(35)
如果在查找路由表时发现有多个选项匹配,那么应该根据___________(25)原则进行选择。假设路由表有4个表项如下所示,那么与地址139.17.179.92匹配的表项是____________(26)。(25)
在面向对象技术中,(43)是一组具有相同结构、相同服务、共同关系和共同语义的(44)集合,其定义包括名称、属性和操作。(44)
随机试题
心脏骤停的诊断标准是()
()是推动经济全球化的市场因素。
Theatmosphereisalltheairsurroundingtheearth.Withoutit,wewouldbeforcedtoseekshelterfromthesun,astherewould
下列符合高血压的描述是
老年(≥65岁)帕金森病患者,首选药物为()。
以下有关定额的作甩说法正确的是( )。
根据以下资料,回答下列问题。2012年年末,合肥市规模以上工业企业2087户,全年实现工业增加值1653.54亿元,比上年增长17.4%。其中,轻工业增加值653.28亿元,增长16.5%;重工业增加值1000.26亿元,增长18%。战略性新兴产业完成产
在发生全球危机那样的极为紧急的时刻,投机活动猖獗,利率急剧上升,一切都变化不定,保护好自己的财产是至关重要的。管理和经济领域的专家认为:储蓄仍然是最安全的避难所,尽管收益非常低,但是把钱存起来实际上不会遇到风险。即使存款的银行破产,政府也保证归还储户一定数
ReserveBankshaveexpressedaninterestinusingnon-employeeexpertsorconsultantsonbanksupervisionmattersforanumbero
WhichofthefollowingisproperdescriptionformembersofCongress?attitudetowardsBushadministration?plans?
最新回复
(
0
)