首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用贪心法求解0/1背包问题时,(55)能够确保获得最优解。用动态规划方法求解 0/1背包问题时,将“用前i个物品来装容量是X的背包”的0/1背包问题记为KNAP(1,i,X),设fi(x)是KNAP(1,i,X)最优解的效益值,第j个物品的重量和放入背包
利用贪心法求解0/1背包问题时,(55)能够确保获得最优解。用动态规划方法求解 0/1背包问题时,将“用前i个物品来装容量是X的背包”的0/1背包问题记为KNAP(1,i,X),设fi(x)是KNAP(1,i,X)最优解的效益值,第j个物品的重量和放入背包
admin
2008-01-15
63
问题
利用贪心法求解0/1背包问题时,(55)能够确保获得最优解。用动态规划方法求解 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)的过程中使用的递推关系式为(56)。.
选项
A、优先选取重量最小的物品
B、优先选取效益最大的物品
C、优先选取单位重量效益最大的物品
D、没有任何准则
答案
D
解析
本题考查0/1背包问题的动态规划求解方法。
利用贪心法可以解决普通背包问题(即允许将物品的一部分装入背包),此时使用“优先选取单位重量效益最大的物品”的量度标准可以获得问题最优解,但是贪心法不能用来求解0/1背包问题,题目中供选择的A、B、C三种量度标准均不能确保获得最优解。
利用动态规划求解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)最优解的值为以上两种情况中效益值更大者,即取max。
转载请注明原文地址:https://kaotiyun.com/show/QbxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在WindowsServer2003的“路由和远程访问”中提供两种隧道协议来实现VPN服务:(1)和L2TP,L2TP协议将数据封装在(2)协议帧中进行传输。 在服务器1中,利用WindowsServer2003的管理工具打开“路由和远程访问
阅读以下说明,回答问题1~3,将答案填入对应的解答栏内。某公司设置VPN服务器允许外地的公司员工通过Internet连接到公司内部网络,如图4-1所示。VPN路由器配置如下,请解释画线部分含义:Vpdn-group1
阅读以下说明,回答问题1至问题4,[说明]终端服务可以使客户远程操作服务器,WindowsServer2003中开启终端服务时需要分别安装终端服务的服务器端和客户端,图3-1为客户机Host1连接终端服务器Server1的网络拓扑示意
IPSec安全体系结构包括AH,ESP和ISAKMP/Oakley等协议。其中,(4)为IP包提供信息源验证和报文完整性验证,但不支持加密服务;(5)提供加密服务;(6)提供密钥管理服务。(5)
IPSec安全体系结构包括AH,ESP和ISAKMP/Oakley等协议。其中,(4)为IP包提供信息源验证和报文完整性验证,但不支持加密服务;(5)提供加密服务;(6)提供密钥管理服务。(4)
若一个项目由9个主要任务构成,其计划图(如下图所示)展示了任务之间的前后关系以及每个任务所需天数,该项目的关键路径是(6),完成项目所需的最短时间是(7)天。
如果用计量器(Gauge)作为某接口到达分组数的对象类型,根据SNMPv1,当该计量器已达到最大值时,若又有一个分组到达,则该计量器的值为(36)。
文法G=({E),{+,*,(,),a},P,E),其中P由下列产生式组成E->E+E|E*E|(E)|a。它生成由a,+,*,(,)组成的算术表达式,该文法在乔姆斯基分层中属于(16)型文法,其对应的自动机是(17),如产生句子a*a+a,它的派生树是(
The approach we propose is a system-oriented methodology for knowledge acquisition. This orientation emphasizes ongoing document
VirtualizationisanapproachtoITthatpoolsandshares(1)sothatutilizationisoptimizedandsuppliesautomaticallymeetd
随机试题
A.青蒿素B.薄荷油C.穿心莲内酯D.甘草酸E.紫杉醇属于三萜的是
我国宪法规定的公民在法律面前一律平等原则的含义是()
李某向保险公司投保家庭财产保险,在保险期间李家被盗,损失财物总计7万余元。李某为获取更多的赔偿,向保险公司谎称被盗财物价值10万元,保险公司全额进行了理赔。事后,保险公司查出李某谎报损失一事。关于如何处理此事,保险公司内部形成以,下列几种意见正确的是:
甲向乙借款10万元,由丙作为保证人,约定“如果甲到期不能偿还该债务,由丙承担保证责任,直至甲的债务本息还清为止”。下列哪些选项是正确的?()
一个总体中各单位至少会有一个不变标志。()
设备的综合利用率是()。
【2012年烟台市市直真题】在教师的人格特征中,有两个重要特征对教学效果有显著的影响,一是教师的热心和同情心,二是教师的()。
西方教育史上第一个将教育与生产劳动相结合思想付诸实践的教育家是()。
根据网络拓扑和需求说明,解释路由器R3的ISATAP隧道配置。R3(config)#interfacetunnel0(7)R3(config-if)#ipv6address2003:DA8:8000:3::/64
下列叙述中正确的是( )。
最新回复
(
0
)