首页
登录
从业资格
考虑一个背包问题,共有n=5个物品,背包容量为W=10,物品的重量和价值分别为:
考虑一个背包问题,共有n=5个物品,背包容量为W=10,物品的重量和价值分别为:
题库
2022-08-02
68
问题
考虑一个背包问题,共有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选项A.11B.14C.15D.16.67问题2选项A.Θ(nW)B.Θ(nlgn)C.Θ(n2)D.Θ(nlgnW)问题3选项A.11B.14C.15D.16.67问题4选项A.Θ(nW)B.Θ(nlgn)C.Θ(n2)D.Θ(nlgnW)
选项
答案
CADB
解析
这是典型的01背包问题,动态规划算法中,自底向上(递推):从小范围递推计算到大范围,可以看到装第一个和第五个物品价值是最高的,这时候V=12了,然后占了6的重量了,只能装物品2了,价值15。
而此时的算法过程是对物品n和背包容量W分别进行比较以找到最优结果,因此时间复杂度为Θ(nW)。
空(3)(4)是部分背包,部分背包的时候计算每个物品单位重量价值多少,单位重量v={3 1.5 5/6 0.8 1.5},可以看到1 2 5的单位价值最高,选择125后背包重量还只有8,还有2个重量可以选择3得等5/3的价值,就是1.67,所以第三问为16.67。
再来看时间复杂度,本题先进行归并排序,然后再根据有序序列来选择放入背包的物品,因此算法分两部分,首先是归并排序时间复杂度为Θ(nlgn),然后是放背包,因为已经排过序,所以只需要线性处理即可,此时时间复杂度为Θ(n),综合起来,由于Θ(nlgn)>Θ(n),因此整体时间复杂度为Θ(nlgn)。
转载请注明原文地址:https://tihaiku.com/congyezige/2410389.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
鱼骨图法是分析问题原因常用的方法之一。鱼骨图就是将系统或服务的故障或者问题作为“
问题管理和控制的目标主要体现在三点。下列选项中,()不在问题管理和控制目标的三
鱼骨图法是分析问题原因常用的方法之一。鱼骨图就是将系统或服务的故障或者问题作为“
故障是系统运行出现的任何系统本身的问题或者任何不符合标准的操作,已经或者可能引起
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】目前我
Sony经验最为可贵的一条就是:如果不把问题细化到SLA的层面,空谈外包才是最大
Sony经验最为可贵的一条就是:如果不把问题细化到SLA的层面,空谈外包才是最大
为IT服务定价是计费管理的关键问题。其中现行价格法是指()。A.参照现有组织内
分布式环境下的系统管理是一个复杂的问题,采用分布式的系统管理可以解决很多问题,其
阅读下列说明,回答问题l至问题3,将解答填入答题纸的对应栏内。【说明】项目是一件
随机试题
Atschoolwewentoveroursocialnetworkingguidelines.(1)_____theobvious
Colorsaresometimescalledhot,cold,orneutral(中性的).Redandyellowares
PopulationGrowthRatesPopulationshav
[originaltext]W:Whathaveyoubeenuptorecently?M:Burningthemidnightoil
[originaltext]W:IsuggestwetakeLindawithus.Whatdoyouthink?M:Whatev
Manypeoplewonderwhysomemenwanttoliveonthemoon.Itis【1】nottheki
定势对迁移的影响表现为两种:______和______。究竟产生何种影响,取决于
某班参加体育活动的学生有25人,参加音乐活动的有26人,参加美术活动的有24人,
国际金融及其管理2015年年末,某国未清偿外债的余额为2000亿美元.其中1年及
下列选项中,不属于物权变动中物权取得的内容是()。A.基于对无主物的先占而取得所
最新回复
(
0
)