首页
登录
从业资格
考虑一个背包问题,共有n=5个物品,背包容量为W=10,物品的重量和价值分别为:
考虑一个背包问题,共有n=5个物品,背包容量为W=10,物品的重量和价值分别为:
题库
2022-08-02
101
问题
考虑一个背包问题,共有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,将解答填入答题纸的对应栏内。【说明】项目是一件
随机试题
A--NoTurnB--OnSaleorReturnC--PleaseShuttheDoorAfterYouD--ProtectPub
[originaltext]W:Morning,sir.MayIaskwhetherMr.Smithhasfreetimeno
根据我国有关法律、法规规定,劳动者不必缴纳的保险费用有()。A.养老保险费
帕金森病最主要的运动障碍是指:()A.肌肉强直 B.运动缓慢和运动
新生儿黄疸最常见的并发症是A.胆红素脑病 B.体温过低 C.颅内压增高 D
善于补肾阳,益精血,强筋骨的药物是A.淫羊藿 B.菟丝子 C.锁阳
研究药物分析的最终目的是A.提高药品的生产效益 B.保证用药安全、合理、有效
在市场趋势分析中,相关分析法可进一步分为( )。A、指数平滑法 B、简单平均法
甲保险公司在与乙工厂订立保险合同时已经知道乙公司隐瞒投保设备存在隐患的情况,但仍
基础心理学是研究()。 (A)正常成人心理现象的心理学基础学科 (B
最新回复
(
0
)