首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
考虑一个背包问题,共有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
28
问题
考虑一个背包问题,共有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)。
(3)
选项
A、11
B、14
C、15
D、16.67
答案
D
解析
转载请注明原文地址:https://kaotiyun.com/show/G1CZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
通过“Internet信息服务(IIS)管理器”管理单元可以配置FTP服务,若将控制端口设置为2222,则数据端口自动设置为______。
当启用VTP修剪功能后,如果交换端口中加入一个新的VLAN,则立即(59)。
请在下列选项中选择合适的答案,填入图3-1、图3-2的方框a和方框b。B的公钥,B的私钥,摘要算法,A的私钥,A的公钥,会话密钥按照图3-2中的方法发送邮件时,使用不同的密码体制加密消息和消息摘要,请用150字以内文字简要说明这样做的理由。
阅读下列说明,回答问题1、问题2和问题3。[说明]某单位资料室需要建立一个图书管理系统,初步的需求分析结果如下:(1)资料室有图书管理员若干名,他们负责己购入图书的编目和借还工作,每名图书管理员的信息包括工号和姓名;(2)
请使用说明中的术语,给出上图中类Customer和类Person的属性。识别关联的多重度是面向对象建模过程中的一个重要步骤。根据说明中给出的描述,完成图中的(1)~(6)。
根据说明中的描述,使用表3-1给出的类的名称,给出图3-1中的A~F所对应的类。根据图3-2所示的播放器行为UML状态图,给出从“关闭”状态到“播放”状态所经过的最短事件序列(假设电池一开始就是有电的)。
完成下述文件格式:指出在哪些图中遗漏了哪些数据流。回答时请用如下形式之一:XX图中遗漏了XX加工(或文件)流向XX加工(或文件)的XX数据流。XX加工XX遗漏了输入(或输出)数据流XX。
【说明】中国教育科研网受理了许多用户(高校和研究机构)中请在指定IP上开设网络访问业务。网络访问包括国内流量和国际流量。教育科研网管理中心保存了网络访问用户档案和网络访问业务档案。【流程图】下面的流程图描述了该系统的数据处理过程。该系统每天对
己知某类库开发商提供了一套类库,类库中定义了Application类和Document类,它们之间的关系如图16—5所示。其中,Application类表示应用程序自身,而Document类则表示应用程序打开的文档。Application类负责打开一个已有
随机试题
孔子说,一种人“和而不同”,还有一种人“同而不和”。下列角色行为属于“和而不同”的是()。
A.常见于登革热的热型B.常见于伤寒、大叶性肺炎的高热期的热型C.常见于流行性感冒的热型D.常见于败血症、伤寒缓解期的热型E.常见于疟疾、淋巴瘤的热型弛张热
一Rh溶血患儿,出现嗜睡、尖声哭叫、肌张力下降,胆红素上升至342μmol/L该患儿可能发生了
下列属于需要编制环境影响报告书的范围的是()。
混凝土结构施工阶段主要的噪声源是( )。。
Excel中,公式中引用绝对单元格地址,其绝对地址不会随公式位置的改变而改变。()
太原某街口出现了一段“最牛”盲道,这段盲道共长200多米,被分成很多长度不一直角拐弯段,百米内共有35处Z字拐弯段。盲道本来是为了盲人而修建的,现在却非常不利于盲人行走,这种做法侵犯了盲人的()
国家新闻出版总署等八大部委联合宣布,“网络游戏防沉迷系统”及配套的《网络游戏防沉迷系统实名认证方案》于2007年正式实施,未成年人玩网络游戏超过5小时,经验值和收益将计为0。这一方案的实施,将有效地防止未成年人沉迷于网络游戏。以下哪项说法如果正确
联结主义学习理论认为()
某办公室5人中有2人精通德语。如从中任意选出3人,其中恰有1人精通德语的概率是多少?
最新回复
(
0
)