首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2013年上半年上午试题60、61)考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如表9.2所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了________(60)设计策略
(2013年上半年上午试题60、61)考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如表9.2所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了________(60)设计策略
admin
2021-01-13
80
问题
(2013年上半年上午试题60、61)考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如表9.2所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了________(60)设计策略。考虑0/1背包问题(每件物品或者全部装入背包或者不装入背包)和部分背包问题(物品可以部分装入背包),求解该实例得到的最大价值分别为________(61)。
(60)
选项
A、分治
B、贪心
C、动态规划
D、回溯
答案
B
解析
本题考查贪心算法和背包问题的知识点。
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题能产生整体最优解或者是整体最优解的近似解。
考虑0/1背包问题时,只能放入1、2、3号物品,故总价值为430;考虑部分背包问题时,可以将物品拆分,故放入1、2、3号物品后还可以将编号4的物品部分地装入,使得背包容量尽量地满,故总容量为630。
转载请注明原文地址:https://kaotiyun.com/show/63CZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某汽车数字仪表系统将完成下述功能:(1)通过模.数转换,实现传感器和微处理器的接口。(2)在发光二极管面板上显示数据。(3)指示速度(mph)、行驶里程、油耗(mpg)等。
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某汽车数字仪表系统将完成下述功能:(1)通过模.数转换,实现传感器和微处理器的接口。(2)在发光二极管面板上显示数据。(3)指示速度(mph)、行驶里程、油耗(mpg)等。
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某大型旅店为了便于管理,欲开发一个客房管理系统。希望实现客房预定、入住登记、帐务结算、退房,以及将服务项目记入客人帐单。旅客包括散客和团体,散客预定或入住时需要提供姓名、性别、身
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸对应栏内。【说明】若要在N个城市之间建立通信网络,只需要N—1条线路即可。如何以最低的经济代价建设这个网络,是一个网的最小生成树的问题。现要在8个城市间建立通信网络,其问拓扑结构如图5—1所示,
阅读下列说明和图,回答问题l至问题3,将解答填入答题纸对应栏内。【说明】某城市拟开发一个基于web的城市黄页,公开发布该城市重要的组织或机构(以F统称为客户)的基本信息,方便城市生活。该系统的主要功能描述如下:(1)搜索信息:任何使用Internet的
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的第m
虚拟存储管理系统的基础是程序的(23)理论,这个理论的基本含义是指程序执行时往往会不均匀地访问主存储器单元。根据这个理论,Denning提出了工作集理论。工作集是进程运行时被频繁访问的页面集合。在进程运行时,如果它的工作集页面都在(24),内,能够使该进程
在一个单CPU的计算机系统中,有两台外部设备R1、R2和三个进程P1、P2、P3。系统采用可剥夺式优先级的进程调度方案,且所有进程可以并行使用I/O设备,三个进程的优先级、使用设备的先后顺序和占用设备时间如下表所示:假设操作系统的开销忽略不计,三个进程
某仓库有两名发货员,一名审核员。当顾客提货时,只要发货员空闲,允许顾客进入仓库提货,顾客离开时,审核员检验顾客提货是否正确。其工作流程如右下图所示。为了利用PV操作正确地协调他们之间的工作,设置了两个信号量S1和S2,且S1的初值为2, S2的初值为1。图
特洛伊木马一般分为服务器端和客户端,如果攻击主机为X,目标主机为Y,则(8)。
随机试题
罐头食品中总干物质的测定用到的细砂一般为100目海砂。
酶促反应动力学研究的是
关于法与道德的论述,下列哪些说法是正确的?(卷一/2009年第55题)
对于因重大误解订立的合同和在订立时显失公平的合同,当事人任何一方均有权向人民法院或者仲裁机构请求变更或者撤销合同。( )
如果用一个圆来表示词语所指称的对象,则以下哪项中三个词语之间的关系符合下图?()
案例:某公司现有普通股100万股,每股面额10元,股本总额为1000万元,公司债券为600万元(总面值为600万元,票面利率为12%,3年期限)。2016年该公司拟扩大经营规模,需增加筹资750万元,现有两种备选方案可供选择:甲方案是增加每股面
そのパソコン、いくら______買ったんですか。
WalkaQuarter-MileorDieIfyoucanwalkaquarter-mile,odds(可能性)areyouhaveatleastsixyearsoflifeleftinyou,sc
•Readthefollowingarticleaboutcareerdevelopmentandthequestionsontheoppositepage.•Foreachquestion15-20,mark
Today,anestimatedtwo-thirdsofallproductsinsupermarketscontaingenetically-engineeredingredients,includingtortillach
最新回复
(
0
)