首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
用动态规划方法求解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
59
问题
用动态规划方法求解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
软件设计师上午基础知识考试
软考中级
相关试题推荐
设信道的码元速率为400波特,采用4相DPSK调制,则信道的数据速率为(26)bit/s。
假设一个有3个盘片的硬盘,共有4个记录面,转速为7200r/min,盘面有效记录区域的外直径为30cm,内直径为10cm,记录位密度为250bit/mm,磁道密度为8道/mm,每磁道分为16个扇区,每扇区512字节,则该硬盘的非格式化容量和格式化容量约为(
ISDN是在(58)基础上建立起来的网络,能够提供的最高速率(59)。常用的有D和B两种标准化信道,其中D信道主要用来传输(60)。使用基本速率接口传输声音,一路话音占用的数据传输率是(61),占总带宽的比例是(62)。
PPP协议是数据链路层的一个协议,它被广泛用于接入Internet中。PPP协议是一个(53)。帧长为整数个字节。它克服了SLIP协议的缺点,可以进行协商,并且(54)。它可以分成3个层次,其中的网络层协议被称为(55),包括了不同的网络层协议。利用PPP
RS-232-C是目前常见的一种接口标准,它是由(32)提供制定的。该标准在OSI模型中属于(33)层协议标准,通过RS-232-C来连接两个设备最少要连接(34)条线。这个标准的设计数据速率是处理(35)bit/s。(35)bit/s条件下,采用RS-4
为了进行差错控制,必须对传送的数据帧进行校验。在局域网中广泛使用的校验方法是(7)校验。CRC-16标准规定的生成多项式为G(x)=X16+X15+X2+1,它产生的校验码是(8)位,接收端发现错误后采取的措施是(9)。如果CRC的生成多项式为G(X)=X
为了进行差错控制,必须对传送的数据帧进行校验。在局域网中广泛使用的校验方法是(7)校验。CRC-16标准规定的生成多项式为G(x)=X16+X15+X2+1,它产生的校验码是(8)位,接收端发现错误后采取的措施是(9)。如果CRC的生成多项式为G(X)=X
SNMPc是一个通用的多用户分布式网络管理平台,采用(21)轮询机制,具有高度的可伸缩性。假设有一个局域网,管理站每15分钟轮询被管理设备一次,一次查询访问需要的时间是200ms,则管理站最多可以支持(22)台网络设备。
在CSMA中,决定退让时间的算法如下(1)如果信道空闲,则以P的概率发送,而以1-P的概率延迟一个时间单位to(2)如果信道忙,则继续监听直至信道空闲并重复步骤(1)。(3)如果发送延迟了一个时间单位t,则重复步骤(1)。上
某计算机有14条指令,其使用频度如表2.10所示。这14条指令的指令操作码用等长码方式编码,其编码的码长至少为(10)位。若只用两种码长的扩展操作码编码,则其平均码长至少为(11)位。
随机试题
下列各种类型的骨折中属于不稳定骨折的是
慢性心功能不全最常见的原因是
xy’’=(1+2x2)y’的通解是()。
某施工单位承接了一段二级道路施工,其中包括3道结构形式和工程量基本相同的涵洞。根据工期要求,对于3道涵洞施工要求组织几个相同的工作队,在同一时间、不同的空间上进行施工。按照资源计划的要求,施工涵洞时安排的技术工人主要有测量工、机修工、钢筋工、木工、混凝
下列选项中,属于客观公正的基本要求的有()。
某冰箱生产企业在市场上推出了一种只卖1999元的经济型产品,而它的高档产品要卖3万多元,从而在吸引顾客来看经济型冰箱时,尽力设法影响他们购买更高档的冰箱。该企业产品大类决策属于()。
依据()可以将学习划分为意义学习与机械学习。
在抗击外国侵略的战争中,许多爱国官兵英勇献身。其中,在第二次鸦片战争中以身殉国的是()。
汉代由皇帝下诏责成中央和地方各级长官每年向朝廷推荐贤能之人为官的选任制度是()。
A、Allwhalingisbad.B、Commercialwhalingisimmoral.C、Whalingshouldbelimitedonlyforfood.D、TheIWCshouldbereplaced.
最新回复
(
0
)