首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
考虑一个背包问题,共有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
37
问题
考虑一个背包问题,共有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)。
(2)
选项
A、Θ(nW)
B、Θ(nlgn)
C、Θ(n
2
)
D、Θ(nlgnW)
答案
A
解析
转载请注明原文地址:https://kaotiyun.com/show/F1CZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
以太网的数据帧封装如下图所示,包含在IP数据报中的数据部分最长应该是(23)________________字节。
计算机采用分级存储体系的主要目的是为了解决()的问题。
计算机内存一般分为静态数据区、代码区、栈区和堆区,若某指令的操作数之一采用立即数寻址方式,则该操作数位于__________。(2008年下半年试题)
阅读以下说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。说明类Queue表示队列,类中的方法如下表所示。类Node表示队列中的元素;类EmptyQueueException给出了队列操作中的异常处理操作。Java代码
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】在并发系统设计中,通过对信号量S的P、V操作实现进程的同步与互斥控制。P(S):S:=S-1,若S≥0,则执行P操作的进程继续执行:若S<0,则置该进程为阻塞状态,
根据E-R图中给出的词汇,按照“关系模式名(属性,属性,…)”的格式,将此E-R图转换为4个关系模式,并指出每个关系模式中的主码和外码,其中模式名根据需要取实体名或联系名。如下的SQL语句是书店用于查询“所有订购了bid为‘123-456’图书的用户
经过进一步分析,设计人员决定定义一个类Itemsonloan,以表示类Book和CD的共有属性和方法。请采用图1-2中属性和方法的名称给出类Items_on_loan应该具有的属性和方法(注意:不同名称的属性和方法表示不同的含义,如CD中的compos
请用120字以内文字,从业务的继承性、升级成本(时间、工作量)和扩展性三个方面简要说明开发人员所提方案的优点。服务注册中心、服务提供者和服务请求者之间的交互和操作构成了WebService的体系结构,如下图所示。请用180字以内文字,说明这三者的主要
写出SQL语句,将记录(ID,Category==pot,DelSize=1.5)插入Delivery表中。写出SQL语句实现如下功能:查询以花瓶(pot)形式发货的所有鲜花的ID、普通名及花瓶的规格,得到结果表按照普通名的字母逆序打印。
阅读下列说明和图,回答以下问题,将解答填入答题纸的对应栏内。【说明】某医疗器械公司作为复杂医疗产品的集成商,必须保持高质量部件的及时供应。为了实现这一目标,该公司欲开发一采购系统。系统的主要功能如下。1.检查库存水平。采购部门每天检查部件库存量,当特
随机试题
四边孔
妊娠合并心脏病,其发病率最高的是
下列选项中不属于行政诉讼受案范围的是()。
生物与其生存环境之间或生物与生物之间的相对状态或相互关系指的是()。
对于R717蒸汽压缩式制冷系统,其出水温度为37℃,制冷量为900kW,则为该系统所配的空气分离器的简体直径应为()mm。
电梯的()应当对电梯质量及投入运行后的维修保养负责。
根据我国《环境影响评价法》的规定,下列表述中正确的是( )。
设计概算可分为以下三级()。
下列各项中属于专门机关与广大群众相结合社会工程中警民结合形式的是()。
角色过载冲突是指一个人的角色要求太多,工作量太大,不可能完成所有觉得所要求的工作时所面临的冲突。根据上述定义,下列属于角色过载冲突的是?
最新回复
(
0
)