首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,填入(n)处字句,并回答相应问题。 [说明] 背包问题就是有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,而且选中物品的价值之和为最大。 背包问题是
阅读下列函数说明和C代码,填入(n)处字句,并回答相应问题。 [说明] 背包问题就是有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,而且选中物品的价值之和为最大。 背包问题是
admin
2009-02-15
26
问题
阅读下列函数说明和C代码,填入(n)处字句,并回答相应问题。
[说明]
背包问题就是有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,而且选中物品的价值之和为最大。
背包问题是一个典型的NP完全难题。对该问题求解方法的研究无论是在理论上,还是在实践中都具有一定的意义。如管理中的资源分配、投资决策、装载问题等均可建模为背包问题。
常用的背包问题求解方法很多,但本题中采用了一种新的算法来求解背包问题。该算法思想为:首先要对物品进行价重比排序,然后按价重比从大到小依次装进包裹。这种方法并不能找到最佳的方案,因为有某些特殊情况存在,但只要把包中重量最大的物品取出,继续装入,直到达到limitweight,这时的物品就是limit weight的最大价值。这种算法不需要逐个进行试探,所以在数据非常大时,执行效率主要由排序的时间复杂度决定。该算法的流程图为图11-4。
仔细阅读程序说明和C程序流程图及源码,回答问题1和问题2。
[流程图11-4]
[程序说明]
struct Thing:物品结构
typedef struct Bag:背包结构类型
input ( ):将物品按序号依次存入数组函数
inbag ( ):物品按物价比入包函数
init ( ):初始化函数
sort ( ):对物品按价格重量比排序函数
outbag ( ):取出包中weiht最大的物品函数
print ( ):最佳方案输出函数
[C程序]
#define N 255
struct Thing {
double weight;
double value;
double dens;
}thing[N];
typedef stmct Bag {
Thing thing [N];
double weighttmp;
double sumvalue;
}bag,best;
inbag ( )
{
do{
bag.thing
=thing
(1)
(2)
i++;
}while ( (3) )
}
init ( )
{
for (inti=0; i<N; i++)
{
input (thing
.weight, thing
.value)
thing
.dens=thing
.value/thing
.weight;
};
}
main ( )
{
init ( );
sort ( );
inbag ( );
do {
best=bag; //把包中物品放入暂存数组
outbag ( ); //取出包中weight最大的物品
(4)
}while ( (5))
print (best); //输出temp因为是最佳方案
}
选项
答案
(1)bag.weighttmp=bag.weighttmp+thing[i].weight; (2)bag.sumvalue=bag.sumvalue+thing[i].value; (3)bag.weighttmp<=weightlimit (4)inbag( ); (5)best.sumvalue<bag.sumvalue
解析
转载请注明原文地址:https://kaotiyun.com/show/vgDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
以下对用户口令进行限定的措施中,(66)对提高安全性来说是无用的。
两名以上的申请人分别就同样的发明创造申请专利时,专利权授权给(35)。
关于软件测试与软件开发的认识,不正确的是______。A.软件生命周期各个阶段都可能产生错误B.软件测试是独立于软件开发的一个工作C.软件开发的需求分析和设计阶段就应开始测试工作D.测试越早进行,越有助于提高被测软件的质量
零件关系P(零件名,条形码,供应商,产地,价格)中的(12)属性可以作为该关系的主键。查询产于西安且名称为“P2”的零件,结果以零件名、供应商及零件价格分列表示,对应的SQL语句为:SELECT零件名,供应商,价格FROMPWHE
()不属于程序的基本控制结构。
某财务系统在使用过程中,因个人所得税政策变化,需修改计算工资的程序。这种修改属于______维护。
线性表采用单循环链表存储的主要优点是_______。
某文件管理系统采用位示图(bitmap)记录磁盘的使用情况。如果系统的字长为32位,磁盘物理块的大小为4MB,物理块依次编号为:0、1、2、…,位示图字依次编号为:0、1、2、…,那么16385号物理块的使用情况在位示图中的第(24)个字中描述;如果磁盘的
系统交付后,修改偶尔会出现乱码的问题,该行为属于________________维护。
阅读以下说明,回答问题1至问题4。【说明】网络工程师经常会面对服务器性能不足的问题,尤其是网络系统中的核心资源服务器,其数据流量和计算强度之大,使得单一计算机无法承担。可以部署多台Linux服务器组成服务器集群,采用负载均衡技术提供服务。
随机试题
大容量变压器效率可达()。
患者男,61岁。冠心病7年,6小时前胸骨后剧痛,为压榨性,并向左臂放射,先后含硝酸甘油2次,疼痛稍缓解,烦躁不安,出汗。查体:急性痛苦面容,体温36.5℃,血压100/70mmHg,脉率100次/分,心界不大,律齐,心音低,未闻及奔马律及杂音,双肺少许湿啰
()为其所在省级行政区域内中小微企业证券非公开发行、转让及相关活动提供基础设施与服务的场所。
根据《中华人民共和国中外合作经营企业法》的规定,1/3以上董事可以提议召开董事会临时会议。()
Therequirementsforhighschoolgraduationhavejustchangedinmycommunity.Asaresult,allstudentsmust【C1】______sixtyhou
NetCostontheRiseCompaniesarepayingupto$10.000toregisteradomainnameontheInterneteventhoughthereisno
某注册会计师协会培训部的魏老师正在准备有关审计业务档案管理的培训课件,她的助手已搜集并整理了一份相关资料存放在Word文档“PPT素材.docx”中,按下列要求帮助魏老师完成PPT课件的整合制作:将演示文稿按下列要求分为3节,分别为每节应用不同的设计主
From2007to2010,Americanhouseholdslost$11trillioninrealestate,savings,andstocks.MorethanhalfofallU.S.worker
Ascivilizationproceedsinthedirectionoftechnology,itpassesthepointofsupplyingallthebasicnecessitiesoflife-food
A、StudentsfromAmerica.B、StudentsfromEngland.C、StudentsfromAustralia.D、StudentsfromJapan.A
最新回复
(
0
)