首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
考虑一个背包问题,共有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
30
问题
考虑一个背包问题,共有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)。
(1)
选项
A、1 1
B、14
C、15
D、1 6.67
答案
C
解析
转载请注明原文地址:https://kaotiyun.com/show/U1CZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
下面关于交换机的说法中,正确的是__________。(2010年下半年试题)
若某条无条件转移汇编指令采用直接寻址,则该指令的功能是将指令中的地址码送入______。
阅读以下说明和数据流图,回答问题1~问题3。【说明】学生住宿服务系统帮助学生在就学的缄市内找到所需的住房,系统对出租的房屋信息、房主信息、需要租房的学生信息以及学生和房主的会面信息进行管理和维护。房主信息包括姓名、地址、电话号码以及系统分
根据题意,补充图2-3中(a)处的空缺,即货物关系模式的属性。写出每种关系模式的主键。
根据题意,补充图2-3中(a)处的空缺,即货物关系模式的属性。根据题意,补充图2-5中缺失的联系和联系的类型,使其成为完善的实体联系图。其中,联系名分别取名为联系1,联系2,联系3,……。
根据以上说明设计的实体联系图如下图所示,请指出读者与图书、书目与读者、书目与图书之间的联系类型。请指出问题2中给出的读者、书目关系模式的主键,以及图书、借还记录和预约登记关系模式的主键和外键。
根据说明中的描述,使用表3-1给出的类的名称,给出图3-1中的A~F所对应的类。根据图3-2所示的播放器行为UML状态图,给出从“关闭”状态到“播放”状态所经过的最短事件序列(假设电池一开始就是有电的)。
填充流程图中①的判断条件。中缀表达式(A+B-C*D)*(E-F)/G经该流程图处理后的输出是什么?[*]
阅读以下说明和C++程序代码,将程序填充完整。【说明】有时我们希望给某个对象而不是整个类添加一些功能。例如,一个图形用户界面工具箱允许你对任意一个用户界面组件添加一些特性,例如边框,或是一些行为,例如窗口滚动。使用继承机制是添加功能的一种
随机试题
拔出胸腔闭式引流管的指征
咳喘无力、气短乏力,多见于咳吐清稀泡沫痰、倚息不得平卧,多见于
某使用国有资金的建设项目,工程建设投资额约15000万元,其中建筑工程费为8000万元,建设单位按规定委托一家招标代理机构代理招标。在招标过程中,发生了以下事件。事件1:在完成项目审批手续,自有资金已到位,初步设计概算已完成,银行贷款资金正在积极落实的条
根据《环境影响评价公众参与暂行办法》,环境保护行政主管部门应当在(),在其政府网站或者采用其他便利公众知悉的方式,公告有关信息。
根据数据的来源不同,风险管理信息系统的风险数据可以分为()。
()是一个以山水石景为依托,吴越遗迹、第宅园林为主的景区,有“聚宝盆”美称。
足球之于巴西,不仅是一项运动,也是一种生活方式,甚至是国家认同的基础。因此,通过足球可以更好地认识、_________巴西和巴西人。为此,我们走进了马拉卡纳,走进了那些百年俱乐部,走进贫困的社区,采访众多足球的参与者,寻找这枚打开巴西的钥匙。填入画横线部分
发展社会主义市场经济,进行宏观调控非常重要,我国的宏观调控要以( )。
ABriefHistoryofOnlineShoppingA)WhenAmazon.comopenedforbusiness15yearsago,itwasnothingmorethanafewpeoplepac
A、Experienceisexclusivelyimportantforsuccessintheindustry.B、Itstopmanagementpositionsareheldbywomen.C、Agentsin
最新回复
(
0
)