首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,填入(n)处字句,并回答相应问题。 [说明] 背包问题就是有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,而且选中物品的价值之和为最大。 背包问题是
阅读下列函数说明和C代码,填入(n)处字句,并回答相应问题。 [说明] 背包问题就是有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,而且选中物品的价值之和为最大。 背包问题是
admin
2009-02-15
40
问题
阅读下列函数说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
结构化开发方法中,(35)主要包含对数据结构和算法的设计。对算法设计时,其主要依据来自(36)。描述算法时,(37)不是理想的表达方式。(36)
为了提高计算机磁盘存取效率,通常可以________。
在机器指令的地址字段中,直接指出操作数本身的寻址方式称为___________。
以下关于不同类型的软件测试的叙述,正确的是______。A.单元测试不是模块测试B.多个模块不能平行地独立进行测试,应该顺序执行C.系统测试是检验程序单元或部件之间的接口关系D.确认测试是通过检验和/或核查所提供的客观证据,证实软件是否满足特定预期
在进行产品评价时,评价者需要对产品部件进行管理和登记,其完整的登记内容应包括(35)。①部件或文档的唯一标识符。②部件的名称或文档标题。③文档的状态,包括物理状态或变异方面的状态。④请求者提供的版本、配置和日期信息。
以下属于测试停止依据的是______。①测试用例全部执行结束②测试覆盖率达到要求③测试超出了预定时间④查出了预定数目的故障⑤执行了预定的测试方案⑥测试时间不足
软件工程每一个阶段结束前,应该着重对可维护性进行复审。在系统设计阶段的复审期间,应该从(8)出发;评价软件的结构和过程。
在结构化分析方法中,数据流图描述数据在系统中如何被传送或变换,反映系统必须完成的逻辑功能,用于(38)建模。在绘制数据流图时,(39)。(38)
网络开发设计的整个过程分为哪几个阶段?每个阶段各有什么任务?请用流程图的方式说明。
阅读下列说明和流程图2-3,将应填入(n)的字句写在答题纸的对应栏内。【说明】下面的流程图描述了对8位二进制整数求补的算法。该算法的计算过程如下:从二进制数的低位(最右位)开始,依次向高位逐位查看,直到首次遇到“1”时,停止查看。然
随机试题
简述偏头痛的药物治疗。
Sleepisdividedintoperiodsofso-calledREMsleep,characterizedbyrapideyemovementsanddreaming,andlongerperiodsofn
关于CTA成像技术的叙述,下列哪一项是错误的
不属于抗高血压药的一类是
麻杏石甘汤的功效是
直肠的全长应为()
某企业2012~2015年销售收入与其相关情况如下:根据上述资料,回答下列问题:预测当2016年销售收入为1000万元时,企业需要增加的资金为()万元。
态度的结构比较复杂,一般我们认为包括()。
请以“我看见一群年轻人横穿马路……想到此事,我的心情就很沉重”为背景编一个故事。
TheBenefitsofUsingCleanEnergyWiththeenvironment-friendlyconceptgoingdeepintopeople’sheart,theworldnowisde
最新回复
(
0
)