首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
考虑一个背包问题,共有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
20
问题
考虑一个背包问题,共有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
某公司网络的地址是202.110.128.0/17。下面的选项中,__________属于这个网络。(2008年下半年试题)
在数据的分组交换方式中,虚电路技术的主要特点是在数据传输之前,站与站之间建立__________。
阅读以下说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。说明通常情况下,用户可以对应用系统进行配置,并将配置信息保存在配置文件中。应用系统在启动时首先将配置文件加载到内存中,这些内存配置信息应该有且仅有一份。下面的代码应用了单身模式
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某指纹门禁系统的体系结构如图3-1所示,其主要部件有:主机(MainFrame)、锁控器(LockController)、指纹采集器(FingerReader)和电控锁(L
请在下列选项中选择合适的答案,填入图3-1、图3-2的方框a和方框b。B的公钥,B的私钥,摘要算法,A的私钥,A的公钥,会话密钥按照图3-2中的方法发送邮件时,使用不同的密码体制加密消息和消息摘要,请用150字以内文字简要说明这样做的理由。
表10-5所给出的类并不完整,根据[说明]和表10-4,将图10-4中的(a)~(c)处补充完整。识别关联的多重度是面向对象建模过程中的一个重要步骤。根据[说明]中给出的描述,完成图10-4中的(1)~(6)。
根据问题描述,填写上图中(1)~(3)处联系的类型。联系类型分为一对一、一对多和多对多三种,分别使用1:1,1:n或1:*,m:n或*:*表示。若去掉权限表,并将权限表中的操作权限属性放在员工表中(仍保持管理和服务岗位的操作权限规定),则与原有设计相比
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】本程序从正文文件text.in中读入一篇英文短文,统计该短文中不同单词及出现次数,并按词典编辑顺序将单词及出现次数输出到正文文件word.out中。程序用一棵有序二叉树存
已知某类库开发商提供了一套类库,类库中定义了Application类和Document类,它们之间的关系如图16-5所示。其中,Application类表示应用程序自身,而Document类则表示应用程序打开的文档。Application类负责打开一个已有
美国某公司与中国某企业谈技术合作,合同约定使用l项美国专利(获得批准并在有效期内),该项技术未在中国和其他国家申请专利。依照该专利生产的产品()需要向美国公司支付这件美国专利的许可使用费。
随机试题
女性,60岁,误服烧碱后1小时,下列哪项处理不恰当
有关脂类食物来源的叙述,错误的是
教师通过自己长期的辛勤工作,使学生提高了思想品德素养,完善了知识与能力,身体和心理都得到了进一步的发展,这些事实集中反映了教师的()。
在教与学的过程中,要进行有意传递的信息是()。
我国宪法规定的公民在法律面前一律平等原则是指()。
一个盒子里有黑棋子和白棋子若干枚,若取出一枚黑子,则余下的黑子数与白子数之比为9:7,若放回黑子,再取出一枚白子,则余下的黑子数与白子数之比为7:5,那么盒子里原有的黑子数比白子数多:
下列关于RPR技术的描述中,正确的是()。
在窗体上画一个文本框,然后编写如下事件过程:PrivateSubTextLKeyPress(KeyAsciiAsIntegcr)DimcharAsStringchar=Chr(KeyAscii)KeyAscii=Asc(UCase(ch
在设计程序时,应采纳的原则之—是______。
TheFranklinRooseveltcameintopowerintheperiodof_______.
最新回复
(
0
)