首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
考虑一个背包问题,共有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
34
问题
考虑一个背包问题,共有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在数据的分组交换方式中,虚电路技术的主要特点是在数据传输之前,站与站之间建立__________。
采用WindowsServer2003创建一个Web站点,主目录中添加主页文件:index.asp后,在客户机的浏览器地址栏内输入该网站的域名后不能正常访问,则不可能的原因是______。
在Windows的cmd命令窗口中输入(38)命令可以用来诊断域名系统基础结构的信息和查看DNS服务器的IP地址。
通过“Internet信息服务(IIS)管理器”管理单元可以配置FTP服务,若将控制端口设置为2222,则数据端口自动设置为______。
阅读以下说明和C代码,将应填入(n)处。[说明]在一公文处理系统中,开发者定义了一个公文结构OfficeDoc,其中定义了公文应该具有的属性(字段)。当公文的内容或状态发生变化时,与之相关联的DocExplorer结构的值都需要发生改变。一个Of
根据题意,补充图2-3中(a)处的空缺,即货物关系模式的属性。写出每种关系模式的主键。
请采用说明中的词汇,给出数据确认处理所需的数据流在第1层图中的全部可选起点(第0层图和第1层图中均未给出)。请使用数据字典条目定义形式,给出第0层DFD中的“手工分户账”数据流和第1层DFD中的“初录分户账”、“复录分户账”的关系。
【说明】一个图书馆信息管理系统的分析与建模。下面是某图书馆的有关介绍。图书馆雇有若干管理员,各自具有编码、姓名等属性。管理员可上岗,也可下岗。图书馆中备有若干图书,每本图书有书号、书名、出版社、价格等属性。图书馆不定期地购买并注册新
阅读下列函数说明和C++代码,将应填入(n)处的字句写在对应栏内。[说明]在一些大型系统中,大多数的功能在初始化时要花费很多时间,如果在启动的时候,所有功能(包括不用的功能)都要全面初始化的话,会导致应用软件要花很多时间才能启动。因此常
甲公司从市场上购买丙公司生产的部件Q,作为生产甲公司产品的部件。乙公司已经取得部件Q的中国发明权,并许可丙公司生产销售该部件Q。甲公司的行为(10)。
随机试题
Thefailureintheexammadehervery______.
当两种对立的动机并存时,就会发生
下列哪种成分几乎不被重吸收而随尿排出体外()。
以下关于现金流量图绘制规则的描述,正确的是()。
配置有信息系统设备的机房内应设等电位连接网络,对于高频(f>10MHz)信息设备宜采用()。
报关员报关执业禁止行为包括()。
规模较大的机械制造工厂的生产过程是由生产技术准备过程、()、辅助生产过程和生产服务过程所组成。
下列行为中,应认定为抢劫罪的有()。
下列各项是否计入GNP(国民生产总值)?为什么?转移支付。
(1)Corporatescandal,laborreductions,economicrecession.Thepastyearhasbeenasoberingexperiencefortheaverageworker,
最新回复
(
0
)