首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,填入(n)处字句,并回答相应问题。 [说明] 背包问题就是有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,而且选中物品的价值之和为最大。 背包问题是
阅读下列函数说明和C代码,填入(n)处字句,并回答相应问题。 [说明] 背包问题就是有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,而且选中物品的价值之和为最大。 背包问题是
admin
2009-02-15
67
问题
阅读下列函数说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在汇编指令中,操作数在某寄存器中的寻址方式称为______寻址。
以下关于软件测试原则的叙述中,正确的是()。
假设段页式存储管理系统中的地址结构如下图所示,则系统中()。
以下关于模块耦合关系的叙述中,耦合程度最低的是__________(39),其耦合类型为___________(40)耦合。(40)
在结构化分析方法中,利用分层数据流图对系统功能建模。以下关于分层数据流图的叙述中,不正确的是___________(32)。采用数据字典为数据流图中的每个数据流、文件、加工以及组成数据流或文件的数据项进行说明,其条目不包括____________(33)。
在结构化分析方法中,数据流图描述数据在系统中如何被传送或变换,反映系统必须完成的逻辑功能,用于(38)建模。在绘制数据流图时,(39)。(38)
计算机各功能部件之间的合作关系如下图所示。假设图中虚线表示控制流,实线表示数据流,那么a、b和c分别表示(5)。
系统交付后,修改原来打印时总是遗漏最后一行记录的问题,该行为属于______维护。
在一个完整的功能测试过程中,______不属于应该编写的测试文档。A.测试需求文档B.测试用例文档C.测试标准D.问题报告单
ISO/IEC9126《软件工程产品质量》统一了多种质量模型。其中,下述关于软件使用质量的描述,不正确的是______。A.它测量用户在特定环境中能达到其目标的程度,不是测量软件自身的属性B.使用质量的属性分为4个特性:有效性、生产率、安全性和满意度
随机试题
A、肾上腺素B、去甲肾上腺素C、去氧肾上腺素D、间羟胺E、麻黄碱作为去甲肾上腺素的代用品,临床上用于各种休克早期、手术后和脊椎麻醉后低血压的药物是
在主动型日常接待中,公共关系人员应承担哪些义务?
结核菌素试验弱阳性结核菌素试验强阳性
下列关于契约型基金的说法中,错误的是()。
我国证券交易所规定,证券收盘价为当日该证券最后一笔交易的成交价。( )
顾客满意的特性包括________。
①根据乾陵建筑对称布局的特点,“无字碑”与“述圣记碑”显然是在高宗去世时由武则天同时主持竖立的,而这块“无字碑”,自然是武则天预先为自己准备的“功德碑”②无字碑上为何无字,人们对此有种种说法,有无数的人在猜测在探究这千古之谜③墓前立有两块高大雄浑的石碑
设平面区域D由直线y=x,圆x2+y2=2y及y轴所围成,则二重积分xydσ=________。
DescribingthefirsttimeshelaideyesonMabel,thehawkthatwouldformthecenterofherlifeforoverfiveyears,HelenMac
Therewasanearthquakehappened,__________100peopleandwithmoreman300__________.
最新回复
(
0
)