首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
用动态规划方法求解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
79
问题
用动态规划方法求解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
软件设计师上午基础知识考试
软考中级
相关试题推荐
项目管理工具中,将网络方法用于工作计划安排的评审和检查的是(13)。
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
在CSMA中,决定退让时间的算法如下(1)如果信道空闲,则以P的概率发送,而以1-P的概率延迟一个时间单位to(2)如果信道忙,则继续监听直至信道空闲并重复步骤(1)。(3)如果发送延迟了一个时间单位t,则重复步骤(1)。上
内存按字节编址,地址从A4000H到CBFFFH,共有(31)字节。若用存储容量为 32 K×8 bit的存储芯片构成该内存,则至少需要(32)片。
软件设计的主要任务是设计软件的构造、过程和模块,其中软件结构设计的主要任务是要确定(3)。
下列关于OSPF协议的说法不正确的是______。
将图中(1)和(2)空缺名称填写在答题纸对应的解答栏内。使ADSL的传输速率更高有哪两个主要因素?
ISDN相对传统电信网有哪些优点?在路由器和ISDN之间需要加入终端适配器(TA)吗?试说明在什么情况下需要加入TA。
阅读以下说明,回答下面问题。【说明】在atm(asynchronoustransfermode)传输模式中,信息被组织成信元,因包含来自某用户信息的各个信元不需要周期性出现,这种传输模式是异步的。由于atm技术简化了交换过程,去处了不必要
随机试题
作为一种无条件支付命令,支票的种类包括()
估价原则可以使不同的估价师对估价的基本前提具有一致性,对同一估价对象在同一估价目的、同一估价时点下的评估价值趋于相同或近似。()
对于室温下定体摩尔热容CV,m为5R/2的理想气体,在等压膨胀的情况下,系统对外所做的功与从外界吸收的热量之比W/Q等于()。
根据《中华人民共和国环境影响评价法》,以下属于环境影响评价内容的是()。
中国银行业协会是我国的银行业自律组织,主管单位为国务院。()
下列出口货物完税价格确定方法中,符合关税法规定的有()。
马克思主义认识论和唯心主义认识论的区别在于是否承认()。
根据公文的要求,“云政办发[2008]015号”,此发文字号存在的问题是()。
从化学角度分析,生活中的下列做法不正确的是:
唐朝的法律形式中,规定中央政府内部各机构关于行政管理、行政程序及具体办事规则,具有行政法规性质的法律形式是()
最新回复
(
0
)