首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
考虑一个背包问题,共有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
66
问题
考虑一个背包问题,共有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在某并发系统中,有一个发送进程A、一个接收进程B、一个环形缓冲区BUFFER、信号量S1和S2。发送进程不断地产生消息并写入缓冲区BUFFER,接收进程不断地从缓冲区BUFFER取消息。假设发送进程和接收进程可以并发地执行,那么,当缓冲区的容量为N时,如何
阅读以下说明和VisualBasic代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某绘图系统定义了一个抽象类IShape,现有三个类CPoint、CLine和CCircle,它们都具有IShape界面。相应的类图关系如图7-1所示。
(1)数据流图1-1缺少了一条数据流(在图1-2中也未给出该数据流),请给出此数据流的起点和终点,并采用说明中的词汇给出此数据流名。(2)数据流图1-2中缺少了与“查询房屋”加工相关的数据流,请指出此数据流的起点和终点。“安排会面”加工除需要写入会面
阅读以下说明和Java代码,将应填入(n)处。[说明]在一公文处理系统中,开发者定义了一个公文类OfficeDoc,其中定义了公文具有的属性和处理公文的相应方法。当公文的内容或状态发生变化时,关注此OfficeDoc类对象的相应的DocExplo
请用120字以内文字,从业务的继承性、升级成本(时间、工作量)和扩展性三个方面简要说明开发人员所提方案的优点。服务注册中心、服务提供者和服务请求者之间的交互和操作构成了WebService的体系结构,如下图所示。请用180字以内文字,说明这三者的主要
根据以上说明设计的实体联系图如下图所示,请指出读者与图书、书目与读者、书目与图书之间的联系类型。请指出问题2中给出的读者、书目关系模式的主键,以及图书、借还记录和预约登记关系模式的主键和外键。
请使用说明中的术语,给出上图中类Customer和类Person的属性。根据说明中的叙述,抽象出如下表所示的方法,请指出上图中的类Customer-InformationSystem和
阅读以下说明和C代码,将应填入(n)处的字句写在的对应栏内。【说明】在一个简化的绘图程序中,支持的图形种类有点(point)和圆(circle),在设计过程中采用面向对象思想,认为所有的点和圆都是一种图形(shape),并定义了类型shape
阅读下列函数说明和C++代码,将应填入(n)处的字句写在对应栏内。[说明]在一些大型系统中,大多数的功能在初始化时要花费很多时间,如果在启动的时候,所有功能(包括不用的功能)都要全面初始化的话,会导致应用软件要花很多时间才能启动。因此常
阅读以下说明和Java代码,将应填入(n)处的字句写在答题纸对应栏内。【说明】对多个元素的聚合进行遍历访问时,需要依次推移元素,例如对数组通过递增下标的方式,数组下标功能抽象化、一般化的结果就称为迭代器(Iterator)。模式以下程序模拟将书籍(Bo
随机试题
校园文化具有教育功能、社会功能和________。
青年工人张小刚为筹办婚事,到玻璃店买了一块穿衣镜,乘25路公共汽车回家。当车行使到东风路口时,突遇豆花饭店服务员王利用木架车拉着为饭店买的货物横穿马路,驾驶员只好紧急刹车。结果车上乘客几乎全部摔倒,张小刚的穿衣镜也被打碎,划破乘客丁望的脸部,使其误工15天
一个主机带几个荧光屏和键盘,从而供多个用户使用,这叫计算机联网。()
已知某分部工程的进度计划如下图单代号网络计划所示,图中节点表示工作,节点上方的数字为节点编号、中部的字母为工作名称、下方的数字为该工作的持续时间,时间单位为天。根据以上资料,回答下列问题:在该分部工程进度计划实施中,工作H的实际进度比计划进度推迟了
在药片压制工序中,需要控制药片的重量,可采用()。
儿童具有好奇心强、好模仿的特点,这就要求幼儿教师的工作具有()。
2014年1月15日,兰某与黄某二人到金水桥游览。二人手里拿着矿泉水来到金水桥,兰某突然不知被什么东西绊倒,矿泉水随之脱落。黄某见状上前去捡那瓶矿泉水,不小心又被兰某绊倒。此时,两名特警就将黄某、兰某二人扶拉起来,接着民警就将二人带上警车,拉到天安门地区分
(江苏2012C—23)2,3,7,(),121,721
通常,以科学计算为主的计算机,对()要求较高。
Smartfirmscanminimizetheirrisksbyconductingweaknessappraisals,choosingexperiencedsecuritypersonnelandestablishin
最新回复
(
0
)