首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
考虑一个背包问题,共有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
65
问题
考虑一个背包问题,共有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在Linux操作系统中,存放用户账号加密口令的文件是__________。(2009年下半年试题)
SMTP服务器端使用的端口号默认为__________。(2011年下半年试题)
数据流图4-1(住宅安全系统顶层图)中的A和B分别是什么?试说明逻辑数据流图(logicaldataflowdiagram)和物理数据流图(physicaldataflowdiagram)之间的主要差别。
阅读下列说明和数据流图,回答问题1至问题4,将解答填入答题纸的对应栏内。[说明]某基于微处理器的住宅安全系统,使用传感器(如红外探头、摄像头等)来检测各种意外情况,如非法进入、火警、水灾等。房主可以在安装该系统时配置安全监控设备(如
阅读下列说明和E-R图,回答问题1至问题3,将解答填入答题纸的对应栏内。说明某网上订书系统的E-R图(已消除了不必要的冗余)如图2-1所示(图中没有标出主码)。图中实体的说明如表2-1所示,相关属性说明如表2-2所示。一个顾客可以在同一天填写
请在下列选项中选择合适的答案,填入图3-1、图3-2的方框a和方框b。B的公钥,B的私钥,摘要算法,A的私钥,A的公钥,会话密钥按照图3-2中的方法发送邮件时,使用不同的密码体制加密消息和消息摘要,请用150字以内文字简要说明这样做的理由。
在需求分析阶段,采用UML的用例图描述系统功能需求,如图1-6所示。指出图1-6中(1)(2)、(3)、(4)分别是哪个用例?指出UML中全局、局部、参数、自我、投票、广播、创建、注销和临时9个约束对于链接角色、消息和对象的作用。
阅读以下函数说明和Java代码,将应填入(n)处的字句写在对应栏内。【说明】下面的程序先构造Point类,再顺序构造Ball类。由于在类Ball中不能直接存取类Point中的xCoordinate及yCoordinate属性值,Ball中的
甲公司从市场上购买丙公司生产的部件Q,作为生产甲公司产品的部件。乙公司已经取得部件Q的中国发明权,并许可丙公司生产销售该部件Q。甲公司的行为(10)。
随机试题
会计制度的科学性原则是指()
关于基因剔除技术,下面的说法哪个正确
薄层色谱法用于药物鉴别,具有特异性强,但常须采用对照品是因为:
在传统的证券市场上,所谓证券经营机构一般包括:()。
安装完Windows后,桌面上通常出现的图标有( )。
民谣“山西人,大褥套,发财还家盖房置地养老少”反映了古代山西人外出经商的普遍追求。由此可以解释近代晋商衰落的原因是()。
中考前,某中学在操场上组织初三学生进行了一次团体辅导,规定初三学生必须参加。在具体实施中,以班级为单位分组,每组人数在40~50人,活动进行时间为二十分钟,这次团体心理辅导不合理的方面是()
社会原收入水平为1000亿元,消费为800亿元,当收入增加到1200亿元时,消费增加至900亿元,请计算边际消费倾向和边际储蓄倾向。
在一切创新中,前提和关键是
Thousandsofyearsago,inthemiddleofanocean,milesfromthenearestisland,anunderseavolcanobrokeout.Thehotliquid
最新回复
(
0
)