首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
用动态规划方法求解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
53
问题
用动态规划方法求解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部分,且3部分的时间分别是t取指=2ns,t分析=2ns,t执行=1.5ns。则100条指令全部执行完毕需(4)ns。
两个码子之间的海明距为(22)。码是由码子组成的集合,一个码的海明距离指的是(23)。若一个码要求检测3位错,则该码的海明距离应为,(24)。
PPP协议是数据链路层的一个协议,它被广泛用于接入Internet中。PPP协议是一个(53)。帧长为整数个字节。它克服了SLIP协议的缺点,可以进行协商,并且(54)。它可以分成3个层次,其中的网络层协议被称为(55),包括了不同的网络层协议。利用PPP
ICMP是Internet控制协议报文协议,它允许主机或路由器报告(37)和提供有关异常情况的报告。它是(38)的组成部分,其报文格式包括报文头和数据区两部分,其中报文头部分是由—些刨等三个字段组成,字段长度分别为(40)。ICMP可作为询问报文,用来测试
计算机指令系统通常采用多种确定操作数的方式。当操作数直接给出时,这种寻址方式叫作(8),在这种方式下,操作数直接包含在指令中;当操作数的地址由某个指定的变址寄存器的内容与位移量相加得到时,叫作(9);如果操作数的地址是主存中与该指令地址无关的存储单元的内容
下列属于PC机的并行接口工作模式的是(23)。
简述什么是ISDN?依据ISO/OSI参考模型对无线扩频网络设备进行分类,可以分为哪几种类型?用无线扩频设备实现网络互连需要何种配套设备?
阅读以下有关网络设计的叙述,分析网络结构,回答下面问题。某公司从20世纪70年代中期开始使用PC机,曾使用NOVELL网络,现在要着手组建企业网络。经过需求分析和论证,设计出如下网络方案。
原型化方法是—种______ 型的设计过程。
随机试题
WilliamPerkins,his________speakingstylenotwithstanding,haslongbeenseenasthemoderatefaceofhispoliticalparty.A.f
引起呃逆的原因有
可引起听神经损害的药物是()
某男,患肺炎,经抗生素治疗后好转,现症见:干咳少痰,咳嗽声低,气短神疲,身热,手足心热,自汗,心胸烦闷,口渴欲饮,舌红,苔薄黄,脉细数。其治疗宜首选()
保险经纪机构及其分支机构与非法从事保险业务或者保险中介业务的单位或者个人发生保险经纪业务往来的,由中国保监会给予警告,并处( )罚款。
下列关于企业竞争战略说法中,正确的有()。
计算机操作系统是一种()。
教师:有学生最近经常生病,是因为他们长期处于紧张状态。家长:这和紧张无关,是学生们抵抗病菌侵袭的能力低造成的。以下哪项如果为真,最能对家长的观点提出质疑?()
今年以来,某导游被游客投诉的次数比其他导游多出一倍。针对旅游公司认为自己服务不到位的质疑,该导游反驳说,每次针对投诉的调查都说明,这些针对他的投诉只是游客太过挑剔。要使该导游的反驳成立,以下()是必须的假设。①如果游客不是太
A.Whydoweforgetthings?B.Howdowemeasurememory?C.Whatarethestagesmemoryconsistsof?D.Whatisthedifferencebe
最新回复
(
0
)