首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
用动态规划方法求解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
63
问题
用动态规划方法求解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
软件设计师上午基础知识考试
软考中级
相关试题推荐
假设一个有3个盘片的硬盘,共有4个记录面,转速为7200r/min,盘面有效记录区域的外直径为30cm,内直径为10cm,记录位密度为250bit/mm,磁道密度为8道/mm,每磁道分为16个扇区,每扇区512字节,则该硬盘的非格式化容量和格式化容量约为(
为了进行差错控制,必须对传送的数据帧进行校验。在局域网中广泛使用的校验方法是(7)校验。CRC-16标准规定的生成多项式为G(x)=X16+X15+X2+1,它产生的校验码是(8)位,接收端发现错误后采取的措施是(9)。如果CRC的生成多项式为G(X)=X
从事电子商务活动要求具有的技术有(58)。
CMM(软件能力成熟度模型)描述和分析了软件过程能力的发展与改进的程度,确立了一个软件过程成熟程度的分级标准。在初始级,软件过程定义几乎处于无章可循的状态,软件产品的成功往往依赖于个人的努力和机遇;在(44),已建立了基本的项目管理过程,可对成本、进度和功
三个部件的可靠度R分别是0.8,如果三个部件串联则它们构成的系统的可靠度是(29)。
在LAN拓扑机构中,(86)是最古老的一种连接方式,结构是具有中心节点的拓扑;(87)是使用同一媒体或电缆连接所有端用户的一种方式,可以用令牌传递或用CSMA/CD控制媒体访问的拓扑;(88)在LAN中使用较多,仅使用象令牌传递这样的确定性的媒体空转法。
下面是一个简单的使用RAWSOCKET实现的ping程序,填入(n)处。/*simplepingprogram*/structsockaddr_insaddr;intrawsock;unsignedshorti
阅读以下说明,回答下面问题。【说明】二层隧道协议L2TP(1ayer2TunnelingProtocol)是一种基于点对点协议PPP的二层隧道协议。某网络结构如图3.3所示,采用L2TP来实现网络安全。
有一个仓库可以存放P1、P2两种产品,但是每次只能存放一种产品。要求:①w=P1的数量-P2的数量;②-1<w<k(i、k为正整数)。若用P/V操作实现P1和P2产品的入库过程,则至少需要上(26)个同步信号量及(27)个互斥信号量
随机试题
________是求和函数。其语法:SUM(number1,number2,…)
根据他物权设立目的的不同,他物权可分为()
补液试验是取250ml等渗盐水静脉滴注的时间是
急性牙槽脓肿排脓通道对根尖周组织破坏最小的是
牙源性腺样瘤多发年龄为()
某投资者购买了1000元的债券,期限3年,年利率10%,若按单利记息,到期一次还本付息,问3年后该投资者可获得的利息是( )元。
()重点说明项目运营管理情况,设计能力实现情况,项目技术改造情况,项目运营成本和财务状况,产品方案与市场情况。
信度系数在解释个人分数意义时的作用包括()。
在因特网的路由选择协议中,属于外部网络协议的是(27),按固定时间间隔和相邻路由器交换路由表信息的协议是(28)。该协议最大特点是(29),它使用(30)传输信息。此协议报文最大长度、最多可包括的路由数和最大距离分别是(31)。
Wanthappier,better-adjustedkids?Paylessattentiontothem,so【C1】______afamilycoachDavidCode.Hesaysfamiliescentered
最新回复
(
0
)