首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如图8一11所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了(60)设计策略。考虑0/1背包问题(每件物品或者全部装入背包或者不
考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如图8一11所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了(60)设计策略。考虑0/1背包问题(每件物品或者全部装入背包或者不
admin
2019-07-12
54
问题
考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如图8一11所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了(60)设计策略。考虑0/1背包问题(每件物品或者全部装入背包或者不装入背包)和部分背包问题(物品可以部分装入背包),求解该实例得到的最大价值分别为(61)。
(61)
选项
A、605和630
B、605和605
C、430和630
D、630和430
答案
C
解析
本题考查贪心算法和背包问题的知识点。贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。采用0/1背包考虑该问题时,只能放入1、2、3号物品,故总价值为430,采用部分背包可以将物品拆分,故放入1、2、3号物品后还可以将编号4的物品部分的装入,使得背包容量尽量的满,故总容量为630。
转载请注明原文地址:https://kaotiyun.com/show/I6CZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在进行进度安排时,PERT图不能清晰的描述(1),但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、……、J,其PERT如下图所示(A=1表示该任务A的持续时间是1天),则项目X的关键路路径是(2)。(2)
下页图中画出曼彻斯特编码和差分曼彻斯特编码的波形图,实际传送的比特卑为(28)。
HTTP协议中,用于读取一个网页的操作方法为______。
在存储体系中位于主存与CPU之间的高速缓存(Cache)用于存放主存中部分信息的副本,主存地址与Cache地址之间的转换工作________________。
攻击者通过发送一个目的主机已经接收过的报文来达到攻击目的,这种攻击方式属于(42)________________攻击。
在生成树协议(STP)中,根交换机是根据什么来选择的?(60).
网络系统设计过程中,物理网络设计阶段的任务是____________。
在路由器配置过程中,要查看用户输入的最后几条命令,应该输入__________。(2010年下半年试题)
在运行WindowsServer2008R2的DNS服务器上要实现IP地址到主机名的映射,应建立_____________记录。
软件产品的可靠性并不取决于______。
随机试题
下列哪项可引起右室压力负荷过重
A.乙琥胺B.苯妥英钠C.卡马西平D.丙戊酸钠E.苯巴比妥肝毒性较大的抗癫痫药物是
A.胃热津伤B.暴饮暴食C.脾胃虚寒D.饮停于胃E.颅内肿瘤吐势徐缓,吐物清稀的临床意义是
下面哪种说法是错误的
海关对申请注册登记许可的审查时限:受理海关应自受理申请之日起______日内;直属海关应自收到受理海关审查意见之日起______日内。
依据关税的有关规定,特许权使用费应计入完税价格的有()。
从企业的角度,薪酬具有的功能有增值和()。
某县一所中学对面的山坡上发生森林火灾。校长要求全体师生上山灭火,抢救国家财产。有一初三年级的班主任没有带领学生上山灭火。事后,校长在全体教工会上点名批评了该班主任。请问:校长的这种做法是否正确?请用相关法律说明。
小张同学坐在路边,手里拿着一个测速仪,小张先测得一辆车,以5米每秒的速度通过,5分钟之后,又有一辆车,以10米每秒的速度通过,问第二辆车要()分钟可以追上第一辆车?
SQL语言又称为
最新回复
(
0
)