首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
用动态规划方法求解0/1背包问题时,将“用前i个物品来装容量是X的背包”的0/1背包问题记为 KNAP(1,i,X),设fi(X)是KNAP(1,i,X)最优解的效益值,第j个物品的重量和放入背包后取得效益值分别为Wj和巧Pj(j=1~n)。则依次求解f0
用动态规划方法求解0/1背包问题时,将“用前i个物品来装容量是X的背包”的0/1背包问题记为 KNAP(1,i,X),设fi(X)是KNAP(1,i,X)最优解的效益值,第j个物品的重量和放入背包后取得效益值分别为Wj和巧Pj(j=1~n)。则依次求解f0
admin
2010-01-23
56
问题
用动态规划方法求解0/1背包问题时,将“用前i个物品来装容量是X的背包”的0/1背包问题记为 KNAP(1,i,X),设fi(X)是KNAP(1,i,X)最优解的效益值,第j个物品的重量和放入背包后取得效益值分别为Wj和巧Pj(j=1~n)。则依次求解f0(X)、f1(X)、…、fn(X)的过程中使用的递推关系式为(58)。
选项
A、fi(X)=min{fi-1(X),fi-1(X)+pi}
B、fi(X)=min{fi-1(X),fi-1(X-wi)+pi}
C、fi(X)=max{fi-1(X),fi-1(X-wi)+pi}
D、fi(X)=max{fi-1(X-wi),fi-1(X)+pi}
答案
C
解析
利用贪心法可以解决普通背包问题(即允许将物品的一部分装入背包),此时使用“优先选取单位重量效益最大的物品”的量度标准可以获得问题最优解,但是贪心法不能用来求解 0/1背包问题。利用动态规划求解0/1背包问题时,按照题目中约定的记号。KNAP(1,i,X)的最优解来自且仅来自于以下两种情况之一:①第i个物品不装入背包,此时最优解的值就是子问题KNAP(1,i-1,X)的最优解的效益值,即为fi-1(X)。②第i个物品装入背包,此时最优解的值为第i个物品的效益值与子问题KNAP(1,i-1,X-Wi)的最优解效益值之和,即为fi-1(X-wi)+pi。由以上分析可知,KNAP(1,i,X)最优解的值为以上两种情况中效益值的更大者,即fi(X)=max{fi-1(X),fi-1(X-wi)+pi}。
转载请注明原文地址:https://kaotiyun.com/show/8gxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
软件开发中的瀑布模型典型地刻画了软件生存周期的阶段划分,与其最适应的软件开发方法是(9)。
ICMP是Internet控制协议报文协议,它允许主机或路由器报告(37)和提供有关异常情况的报告。它是(38)的组成部分,其报文格式包括报文头和数据区两部分,其中报文头部分是由—些刨等三个字段组成,字段长度分别为(40)。ICMP可作为询问报文,用来测试
(12)是关于质量管理体系的一系列标准,有助于企业交付符合用户质量要求的产品。自标准实施之日起,至标准复审重新确认、修订或废止的时间,称为标准的有效期,我国在国家标准管理办法中规定,国家标准的有效期一般为(13)年。我国著作权法中对公民作品的发表权
为了进行差错控制,必须对传送的数据帧进行校验。在局域网中广泛使用的校验方法是(7)校验。CRC-16标准规定的生成多项式为G(x)=X16+X15+X2+1,它产生的校验码是(8)位,接收端发现错误后采取的措施是(9)。如果CRC的生成多项式为G(X)=X
公开密钥加密是一种(43)。常用的公钥加密算法有(44),它的一个比较知名的应用是(45),这种应用的协商层用公钥方式进行身份认证,记录层涉及到对应用程序提供的信息的分段、压缩、数据认证和加密。
容量为64块的Cache采用组相连方式映像,字块大小为128个字,每4块为一组。若主存容量为4096块,且以字编址,那么主存地址应该为(43)位,主存区号为(44)位。
从工作的频段、数据传输速率、优缺点以及它们之间的兼容性等方面,对IEEE802.11a、IEEE802.11b和IEEE802.11g进行比较。简述WLAN用户通过RADIUS服务器登录的过程。
FDDI(光纤分布式数据接口)的基本编码方法是(168),在此基础上采用(169)编码,编码效率提高到(170)。
下面是一个面向连接的SOCKET实例,填入(n)处。【说明】代码实例中的服务器通过socket连接向客户端发送字符串"Hello,youareconnected!"。只要在服务器上运行该服务器软件,在客户端运行客户软件,客户端就会收到该
在数据通信中,将信道上的模拟信号变换成数字信号的过程称为(26)。
随机试题
(2013.10.16)自然环境中,属于有限但可以更新的资源有()
IliketogetupearlysothatIcangetplentyofwork______beforelunch.
赵某于2004年3月2日与李某签订房屋租赁合同,租期3年。随后赵某与其妻刘某共同居住该房。2004年5月5日,赵某因交通事故死亡,刘某继续留住在该房中,并按约定向李某支付房租。2004年7月6日,李某通知刘某立即搬出该房。经查李某已与王某签订房屋租赁合同,
钢筋拉伸试验,应根据从规范中查出的()指标和测量计算的钢筋横截面面积,估算试验中需要的最大荷载,由此为根据选择合适的试验机测力量程。
关于集体土地所有权主体及代表,下列说法正确的是()。
水泥按其性能及用途可分为( )。
【背景材料】以下是某乡镇政务服务大厅的服务须知:(1)工作时间为上午8点半至下午4点半,中午休息用餐1个小时;(2)大厅一层设置自助查询机.请大家自行在自助机上查找业务负责窗口及办理流程:(3)无需到窗口办理,只需到
试述颜之推关于早期教育的思想。
理解人类社会发展史的“钥匙”是
(2009下集管)风险定量分析是在不确定情况下进行决策的一种量化方法,该过程经常采用的技术有______。
最新回复
(
0
)