首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
考虑一个背包问题,共有n=5个物品,背包容量为W=10,物品的重量和价值分别为:w={2,2,6,5,4},v={6,3,5,4,6},求背包问题的最大装包价值。若此为0一1背包问题,分析该问题具有最优子结构,定义递归式为 其中c(i,j)表示i个物品、
考虑一个背包问题,共有n=5个物品,背包容量为W=10,物品的重量和价值分别为:w={2,2,6,5,4},v={6,3,5,4,6},求背包问题的最大装包价值。若此为0一1背包问题,分析该问题具有最优子结构,定义递归式为 其中c(i,j)表示i个物品、
admin
2019-07-12
46
问题
考虑一个背包问题,共有n=5个物品,背包容量为W=10,物品的重量和价值分别为:w={2,2,6,5,4},v={6,3,5,4,6},求背包问题的最大装包价值。若此为0一1背包问题,分析该问题具有最优子结构,定义递归式为
其中c(i,j)表示i个物品、容量为j的0-1背包问题的最大装包价值,最终要求解c(n,W)。
采用自底向上的动态规划方法求解,得到最大装包价值为(1),算法的时间复杂度为(2)。
若此为部分背包问题,首先采用归并排序算法,根据物品的单位重量价值从大到小排序,然后依次将物品放入背包直至所有物品放入背包中或者背包再无容量,则得到的最大装包价值为(3),算法的时间复杂度为(4)。
(4)
选项
A、Θ(nW)
B、Θ(nlgn)
C、Θ(n
2
)
D、Θ(nlgnW)
答案
B
解析
本题考查算法设计与分析的基础知识。
背包问题是一个经典的计算问题,有很多应用。背包问题有两类,0-1背包问题和部分背包问题。
若用c(i,j)表示i个物品、容量为j的最大装包价值,则0一1背包问题可以用动态规划方法求解,其递归式为:
根据该递归式,自底向上可以计算题干实例中各个子问题的最优解的值,如下表所示。
上表中行表示物品,列表示背包容量,每个元素的值表示,在仅考虑前i个物品时,背包容量为该列对应的值时,所获得的最大价值。
根据上表的结果,得到最大价值为15。
自底向上计算该递归式,在实现时其实是两重循环,物品个数的循环和背包容量的循环,因此时间复杂度为Θ(nW)。
部分背包问题可以用贪心算法求解。首先根据物品的单位重量价值对物品并对其从大到小排序,然后依次取出物品放入背包,直到所有物品装完或者背包不能装入某个物品时,只放入该物品的一部分,让背包装满。单位重量价值如下表。
上表中行表示物品信息,即重量,价值和单位重量价值,列表示对应的物品。
根据贪心策略,首先取出第一个物品放入背包,然后取出第二个物品和第五个物品放入背包,此时获得价值6+3+6=15,背包剩余容量10一2—2—4=8。此时不能将第三个物品全部放入背包,只能放2/6=1/3,对应获得的价值为5*1/3=1.67,因此得到所获得的最大价值为15+1.67=16.67。
若用时间复杂度为Θ(nlgn)的归并排序算法先对物品的单位重量价值排序,然后依次将物品放入背包(时间复杂度为Θ(n)),则整个算法的时间复杂度为Θ(nlgn)。
转载请注明原文地址:https://kaotiyun.com/show/L1CZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在程序执行过程中,Cache与主存的地址映像由(1)。
下面关于交换机的说法中,正确的是__________。(2010年下半年试题)
光纤布线系统的测试指标不包括(30)。
网络拓扑设计对网络的影响主要表现在__________。(2013年上半年试题)①网络性能②系统可靠性③出口带宽④网络协议
数据流图4-1(住宅安全系统顶层图)中的A和B分别是什么?数据流图4-2(住宅安全系统第0层DFD图)中的数据存储“配置信息”会影响图中的哪些加工?
图3-2是该系统类图的一部分,依据上述说明中给出的术语,给出类Lock的主要属性。组装(composition)和聚集(aggregation)是UML中两种非常重要的关系。请说明组装和聚集分别表示什么含义?两者的区别是什么?
根据以上说明设计的实体联系图如下图所示,请指出读者与图书、书目与读者、书目与图书之间的联系类型。该图书管理系统的主要关系模式如下,请补充“借还记录”和“预约登记”关系中的空缺。管理员(工号,姓名)读者(读者ID,姓名,电话,E-mai
根据上述说明和实体-联系图,得到该住房管理系统的关系模式如下所示,请补充住宿关系。房间(房间号,收费标准,床位数目)客人(身份证号,姓名,性别,出生日期,地址)住宿((1),入住日期,退房日期,预付款额)若将上述各关系直接实现为
根据问题描述,填写上图中(1)~(3)处联系的类型。联系类型分为一对一、一对多和多对多三种,分别使用1:1,1:n或1:*,m:n或*:*表示。若去掉权限表,并将权限表中的操作权限属性放在员工表中(仍保持管理和服务岗位的操作权限规定),则与原有设计相比
美国公民Tom于2007年3月1日向中国专利局提出一件实用新型专利申请。其后,Tom对该发明做了改进,于2008年3月1日就其改进发明向中国专利局又提出申请时,可享有(10)。
随机试题
世界人口的增长动态是()
男性的腹股沟斜疝右侧比左侧多见,其原因是
20世纪90年代以来,我国社会福利服务出现()的色彩。
年轻人要有“个人梦”,有“梦”的人才不会沾染暮气。日有所思夜即有所想,梦的内容反映的是追求、体现的是抱负。年轻人“爱做梦”,就不会甘于平庸、随波逐流、行尸走肉。青年一代就应该有自己独有的气质,敢做敢为。那种丢弃梦想,一心进入体制内、安安稳稳排资论辈的思想是
“洋泾浜”一旦被社会采用为主要交际工具。就会发展成为克里奥耳语。()
按覆盖地理范围分,计算机网络可分为广域网与
在VisualFoxPro中,属于表单方法的是()。
A、Right.B、Wrong.C、Doesn’tSay.B
PassageFourAccordingtoParagraphSix,whatbenefitcanthistechnologybring?
Whenitcomestohumanresources,hiringhighly-skilledstaffisnotusuallyenoughforacompanytofunctionsuccessfully.Besi
最新回复
(
0
)