首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2013年上半年上午试题60、61)考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如表9.2所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了________(60)设计策略
(2013年上半年上午试题60、61)考虑下述背包问题的实例。有5件物品,背包容量为100,每件物品的价值和重量如表9.2所示,并已经按照物品的单位重量价值从大到小排好序。根据物品单位重量价值大优先的策略装入背包中,则采用了________(60)设计策略
admin
2021-01-13
54
问题
(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,将解答填入答题纸的对应栏内。【说明】公司IT部门决定开发一个计算机管理系统以记录期刊的传阅情况。期刊在公司内部传阅,员工可以要求加入传阅队列。图书室登记公司收到的期刊,交给名单中的第一名员工。员工应在三个工作日内完
阅读以下说明和Java代码,将应填入(n)处的字句写在答题纸对应栏内。【说明】在一些大型系统中,大多数的功能在初始化时要花费很多时间,如果在启动的时候,所有功能(连不用的功能)都要全面初始化的话,会连带影响到应用软件要花很多时间才能启动。因此常将程序设
阅读以下说明和程序流程图,将应填入(n)处的字句写在答题纸对应栏内。【说明】假定用一个整型数组表示一个长整数,数组的每个元素存储长整数的一位数字,则实际的长整数m表示为:m=a[k]×10k-2+a[k一1]×10k-3+…+a[3]×10+a[2]其
阅读下列说明和E—R图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】建立一个供应商零件数据库,数据库要满足如下要求:(1)供应商代码不能为空,且是值唯一的,供应商的名也是唯一的。(2)零件号不能为空,且值是唯一的,零件号不能为空。(3
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】为了有效记录交通事故情况,欲设计一个交通事故记录系统。一辆汽车有一个唯一的“车牌号”,车主购买汽车时需要提供相关信息,包括身份证、姓名、年龄、性别、地址等。一个车主可以拥有多辆汽
阅读下列说明和数据流图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某供销系统接受顾客的订货单,当库存中某配件的数量小于订购量或库存量低于一定数量时,向供应商发出采货单;当某配件的库存量大于或等于订购量时,或者收到供应商的送货单时并更新了库
阅读以下说明和图,回答问题l至问题3.将解答填入答题纸的对应栏内。【说明】某时装邮购提供商拟开发订单处理系统,用于处理客户通过电话、传真、邮件或web站点所下订单。其主要功能如下:(1)增加客户记录。将新客广信息添加到客户文件,并分配一个客户号以备后
阅读以下说明,根据要求回答问题1~问题3。【说明】某快递公司为了方便管理公司物品运送的各项业务活动,需要构建一个物品运送信息管理系统。【需求分析结果】(1)快递公司有多个分公司,分公司信息包括分公司编号、名称、经理、办公电话和地址。每个分公司可以
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】某应用中需要对100000个整数元素进行排序,每个元素的取值在0~5之间。排序算法的基本思想是:对每一个元素x,确定小于等于x的元素个数(记为m),将x放在输出元素序列的第m
随机试题
其治疗应用:该病失治后可出现下列何种疾病:
休克微循环痉挛期的主要变化是
人民法院受理破产申请后,已经开始而尚未终结的有关债务人的民事诉讼或者仲裁应当中止;在()之后.该诉讼或者仲裁继续进行。
下列市场预测程序中,正确的顺序是()。
下列关于矿产资源的说法中,正确的是()
甲公司是一家光伏生产企业。近几年,我国开始大力发展新能源,出台了若干促进光伏产业发展的政策,光伏产业逐渐发展壮大起来。甲公司也进入了快速发展阶段,销售额和出口额近十年来平均增长15%以上。员工也由原来的不足200人增加到了2000多人。甲公司采用
王某2012年3月取得稿酬20000元,讲课费4000元,已知稿酬所得适用个人所得税税率为20%,并按应纳税额减征30%,劳务报酬所得适用个人所得税税率为20%。根据个人所得税法律制度的规定,王某应缴纳个人所得税额为()元。
简述留置权的含义及成立条件。(2012年简答54)
蟋蟀是一种非常有趣的昆虫。宁静的夏夜,草丛中传来阵阵清脆悦耳的鸣叫声,那是蟋蟀在歌唱。蟋蟀优美动听的歌声并不是出自它的好嗓子,而是来自它的翅膀。左右两翅一张一合,相互摩擦,就可以发出悦耳的声响了。蟋蟀还是建筑专家,与它那柔弱的挖掘工具相比,蟋蟀的住宅真可以
Toitsfans,itisaddictive.Tothemedia,itisapromisingmoney-maker.Sudoku,anoldpuzzlelongpopularinJapanisfastg
最新回复
(
0
)