首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用贪心法求解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
31
问题
利用贪心法求解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
软件设计师上午基础知识考试
软考中级
相关试题推荐
请阅读以下说明和Socket程序,将应填入(n)处的字句写在对应栏内。网络应用的基本模型是客户机/服务器模型,这是一个不对称的编程模型,通信的双方扮演不同的角色:客户机和服务器。一般发起通信请求的应用程序称为客户软件,该应用程序通过与服务器进程
在WindowsServer2003的“路由和远程访问”中提供两种隧道协议来实现VPN服务:(1)和L2TP,L2TP协议将数据封装在(2)协议帧中进行传输。 子公司Pcl安装windowsxP操作系统,打开“网络和Internet连接”。若要
阅读以下说明,回答问题1~3,将答案填入对应的解答栏内。某公司由总部和分支机构构成,通过IPSec实现网络安全,网络拓扑结构如图4-1所示。路由器之间的地址分配如表4-1所示。总部端路由器的部分配置如下,解释配置中语句部
阅读以下说明,回答问题1~5,将解答填入对应的解答栏内。如图5-1所示,为了实现交换机SW1和SW2之间的冗余连接以提高传输速度和可靠性,在这两台交换机使用两条双绞线互连。为了避免网络环路的出现,在两台交换机之间使用了生成树协议(Spanning
阅读以下说明,回答问题1~3,将答案填入对应的解答栏内。网络地址转换(NAT)的主要目的是解决IP地址短缺问题以及实现TCP负载均衡等。在图4-1的设计方案中,与Internet连接的路由器采用网络地址转换。NAT按技术类型分为(10
note-bat脚本文件如下:time/t>>note.lognetstat-n-ptcp|find":3389">>note.logstartExplorer第一行代码用于记录用户登录的时间,“t
该网络采用核心层、汇聚层、接入层的三层架构,所有计算机都采用静态IP地址。为了防止恶意用户盗用IP地址,网管员可采用(3)的策略来防止IP地址盗用,该策略应在三层架构中的(4)层实施。企业架设Web服务器对外进行公司及产品宣传,同时
在网络的拓扑结构中,处于上层的结点称为(36)。只要有一个结点发生故障,网络通信就无法进行的结构是(37);数据单方向传输的拓扑结构是(38)。(39)允许某些站点具有优先级。交换式局域网属于(40)。
WindowsServer2003操作系统中,域用户信息存储于(34)中。(35)不属于WindowsServer2003活动目录的物理结构。
The approach we propose is a system-oriented methodology for knowledge acquisition. This orientation emphasizes ongoing document
随机试题
在串联电路中,总电阻等于各电阻的倒数之和。()
转录过程由RNA聚合酶催化。原核生物的RNA聚合酶只有1种,共包含有α2ββ’σ5个亚基。与转录启动有关的亚基是
关于尿胆红素测定,下列叙述正确的是( )
A.流产感染B.稽留流产C.先兆流产D.难免流产E.不全流产停经11周,少量阴道流血3天,子宫符合孕月,宫口未开
九味羌活丸【处方】羌活150g,防风150g,苍术15%,细辛50g,川芎100g,白芷100g,黄芩100g,甘草100g,地黄100g。【制法】以上九味,粉碎成细粉,过筛,混匀,用水泛丸,干燥,即得。药师甲在制备药物过程中,发现某饮片为类圆形或不规
住宅工程质量分户验收由施工单位负责实施。()
游戏对儿童心理发展的意义在于()。
正常情况下,每个月依照法定程序延长的工作时间不能超过()。
湖北农民彭立成家1974年的春联是“过年只有两升米,压岁并无一分钱”,1983年的春联是“人有勤劳致富两只手,家有吃穿住用四不愁”。春联反映了湖北农村的巨大变化,导致这一变化的主要原因是()。
下列哪种行为可以提出行政复议?()
最新回复
(
0
)