首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
用动态规划方法求解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
82
问题
用动态规划方法求解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)。
两个码子之间的海明距为(22)。码是由码子组成的集合,一个码的海明距离指的是(23)。若一个码要求检测3位错,则该码的海明距离应为,(24)。
PPP协议是数据链路层的一个协议,它被广泛用于接入Internet中。PPP协议是一个(53)。帧长为整数个字节。它克服了SLIP协议的缺点,可以进行协商,并且(54)。它可以分成3个层次,其中的网络层协议被称为(55),包括了不同的网络层协议。利用PPP
ICMP是Internet控制协议报文协议,它允许主机或路由器报告(37)和提供有关异常情况的报告。它是(38)的组成部分,其报文格式包括报文头和数据区两部分,其中报文头部分是由—些刨等三个字段组成,字段长度分别为(40)。ICMP可作为询问报文,用来测试
RS-232-C是目前常见的一种接口标准,它是由(32)提供制定的。该标准在OSI模型中属于(33)层协议标准,通过RS-232-C来连接两个设备最少要连接(34)条线。这个标准的设计数据速率是处理(35)bit/s。(35)bit/s条件下,采用RS-4
在因特网的路由选择协议中,属于外部网络协议的是(27),按固定时间间隔和相邻路由器交换路由表信息的协议是(28)。该协议最大特点是(29),它使用(30)传输信息。此协议报文最大长度、最多可包括的路由数和最大距离分别是(31)。
下列文件中属于逻辑结构文件的是(8)。
计算机指令系统通常采用多种确定操作数的方式。当操作数直接给出时,这种寻址方式叫作(8),在这种方式下,操作数直接包含在指令中;当操作数的地址由某个指定的变址寄存器的内容与位移量相加得到时,叫作(9);如果操作数的地址是主存中与该指令地址无关的存储单元的内容
阅读下列程序说明和C代码,填入(n)处。【说明】幼儿园有n(<20)个孩子围成一圈分糖果。老师先随机地发给每个孩子若干颗糖果,然后按以下规则调整:每个孩子同时将自己手中的糖果分一半给坐在他右边的小朋友。如共有8个孩子,则第1个
随机试题
患者,男性,55岁。在路上行走时,突发意识丧失,大动脉搏动消失,被路人发现,正好有医师经过,该医师判断其为心跳呼吸骤停,速行心肺复苏基础生命支持后转至医院。经过积极的进一步生命支持,患者于数日后清醒出院,但存在偏瘫、构音困难、语言障碍。目前国际上通用的
男性,29岁,口腔溃疡反复发作5年,加重半年。查:舌缘左右侧,各可见两块约1.0~1.2cm的溃疡,边缘不整,表面有灰白色的伪膜。下唇内侧粘膜有条形白色瘢痕。临床应注意与下列哪种疾病相鉴别
一个tRNA反密码子为5’-IGC-3’,它可以识别的密码( )。
A、及时服B、饭前服C、清晨空腹服或睡前服D、睡前1~2h服E、晚上服用治哮喘的药物宜()
在施工进度计划中,工作之间由于劳动力、施工机械、材料和构配件等资源的组织和安排需要而形成的逻辑关系,称为()。
()也是机构了解社工服务品质的重要途径。
个体有控制别人或被别人控制的需要,个体有在权力关系上与他人建立或维持满意人际关系的需要。这种需要是()。
“不登高山,不知天之高也”属于唯物主义的知行观。()
求方程y’’+2my’+n2y=0的通解;又设y=y(x)是满足y(0)=a,y’(0)=b的特解,求y(x)dx,其中m>n>0,a,b为常数.
A、She’sinameeting.B、She’soutoftheoffice.C、She’stalkingwithanothercustomer.D、She’sspendingherholiday.B
最新回复
(
0
)