首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
考虑一个背包问题,共有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
48
问题
考虑一个背包问题,共有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
ISP分配给某公司的地址块为199.34.76.64/28,则该公司得到的地址数是______。
假如有3块容量是300GB的硬盘做RAID5阵列,则这个RAID5的容量是_____________。
阅读下列说明和算法,回答问题1和问题2,将解答填入答题纸的对应栏内。[说明]算法2-1是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号,则给出相应的提示信息,如下所示:文件提示信息(
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某指纹门禁系统的体系结构如图3-1所示,其主要部件有:主机(MainFrame)、锁控器(LockController)、指纹采集器(FingerReader)和电控锁(L
阅读以下说明和C程序,将应填入(n)处的字句写在答题纸的对应栏内。【说明】假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务,但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配1个不同的任
阅读以下说明和表,回答问题1~问题4。【说明】某公司信息管理系统的需求分析和部分关系模式设计的结果描述如下。1.公司有多个部门,每个部门有一名负责人、一间办公室、一部电话、多名职员,每个职员最多属于一个部门,负责人也是一名公司职员。
阅读下列函数说明和C代码,填入(n)处。[说明]以下C语言程序实现了生成从里到外是连续的自然数排列的回旋矩阵,矩阵形式如下:7651681415923
阅读以下说明和Java代码,将应填入(n)处的字句写在对应栏内。[说明]在一些大型系统中,大多数的功能在初始化时要花费很多时间,如果在启动的时候,所有功能(连不用的功能)都要全面初始化的话,会连带影响到应用软件要花很多时间才能启动。因此
当采用标准UML构建系统类模型(Class Model)时,若类B除具有类A的全部特性外,类B还可定义新的特性以及置换类A的部分特性,那么类B与类A具有(46)关系;若类A的对象维持类B对象的引用或指针,并可与类C的对象共享相同的类B的对象,那么类A与类B
随机试题
Ofthetwosisters,Sarais(young)________one,andsheisalsotheonewholovestobequiet.
阅读《长恨歌》中的一段文字,回答问题。蜀江水碧蜀山青,圣主朝朝暮暮情。行宫见月伤心色,夜雨闻铃肠断声。天旋日转回龙驭,到此踌躇不能去。马嵬坡下泥土中,不见玉颜空死处。A.诗中“圣主”、“玉颜”分别指谁?B.这里表
金银花的主要成分不包括
细菌的侵袭力不包括
城市规划中“黄线”是指以下哪个控制界线?[2008年第12题]
期货公司未按期报送风险监管报表,中国证监会派出机构应当()。
应纳税额在人民币()元以下的船舶可以免征吨税。
导入的作用有哪些?以“friendship”为话题为高中课堂设计两种不同的导人方式并说明目的。
下图示意我国某山地的东坡和西坡的垂直带谱。读图完成下列问题。干旱河谷灌丛带所在的河谷终年盛行()。
Angerisanemotionthatcanbehardtocontrol.【C1】_____this,weshouldlearnhowtomanageangerinaconstructivemanner.In
最新回复
(
0
)