首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用贪心法求解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
43
问题
利用贪心法求解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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明,回答问题1~3,将解答填入对应的解答栏内。某公司的分支机构通过一条DDN专线接入到公司总部,地址分配和拓扑结构如图5-1所示。在两台路由器之间可以使用静态路由,也可以使用动态路由。下面是公司总部的路由器R2的配置命令列表,在
阅读以下说明,回答问题1~5,将解答填入对应的解答栏内。如图5-1所示,为了实现交换机SW1和SW2之间的冗余连接以提高传输速度和可靠性,在这两台交换机使用两条双绞线互连。为了避免网络环路的出现,在两台交换机之间使用了生成树协议(Spanning
阅读以下说明,回答问题1~3,将答案填入对应的解答栏内。网络地址转换(NAT)的主要目的是解决IP地址短缺问题以及实现TCP负载均衡等。在图4-1的设计方案中,与Internet连接的路由器采用网络地址转换。此配置中采用的转换方式为(
在WindowsServer2003系统中,用户分为本地用户和域用户,本地用户的安全策略用“本地安全策略”设置,域用户的安全策略通过活动目录管理。在“本地安全设置”中启用了“密码必须符合复杂性要求”功能,如图4-1所示,则用户“ABC”可以采用的密码
阅读以下说明,回答问题1至问题4,[说明]终端服务可以使客户远程操作服务器,WindowsServer2003中开启终端服务时需要分别安装终端服务的服务器端和客户端,图3-1为客户机Host1连接终端服务器Server1的网络拓扑示意
IPSec安全体系结构包括AH,ESP和ISAKMP/Oakley等协议。其中,(4)为IP包提供信息源验证和报文完整性验证,但不支持加密服务;(5)提供加密服务;(6)提供密钥管理服务。(6)
文件/etc/sysconfig/network-scripts/eth0用于存储网络配置信息,请根据图2-1填写下面的空缺信息,完成主机的配置。DEVICE=eth0HWADDR=(7)ONBOOT=yesBOOT
阅读以下说明,回答问题。(2012年上半年下午试题一)[说明]某公司计划部署园区网络,其建筑物分布如图2-10所示。根据需求分析结果,网络规划要求如下。(1)网络中心机房在信息大楼。(2)设计中心由于
若在系统中有若干个互斥资源R,6个并发进程中的每一个都需要两个资源R,那么使系统不发生死锁R的最少数目为()。
随机试题
女,45岁。反复右下腹痛1年,伴便秘、口腔渍疡,无发热及乏力。否认结核病史及结核密切接触史。查体:右下腹可触及边界不清的包块,可移动,压痛阳性。为明确诊断,最重要的检查是()
慢性骨髓炎行死骨摘除术的最佳时机是
男,25岁,低热,干咳1个月。体检:浅表淋巴结无肿大,肺部无异常体征。胸片示右肺门淋巴结肿大,诊断首先考虑
牛慢性脓性子宫内膜炎治疗的有效方法之一是冲洗子宫、排出脓性分泌液、消除感染,恢复子宫机能,下列最有效的冲洗液是()。
关于工作流程图的说法正确的是()。
与其他道路施工相比,机场稳定土(碎石)基区、土面区、升降带和跑道端安全地区等要求有较高的密实度和良好的平整度。民用机场土基密实度则要求达到(重型击实)()以上。
环泵式泡沫比例混合器安装标高的允许偏差为()。
可以使插人点快速移到文档首部的组合键是()。
下列对英国内阁首相表述正确的是()。
自我遵循的原则是()。
最新回复
(
0
)