首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,填入(n)处字句,并回答相应问题。 [说明] 背包问题就是有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,而且选中物品的价值之和为最大。 背包问题是
阅读下列函数说明和C代码,填入(n)处字句,并回答相应问题。 [说明] 背包问题就是有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,而且选中物品的价值之和为最大。 背包问题是
admin
2009-02-15
44
问题
阅读下列函数说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
已知函数f()、g()的定义如下所示,调用函数f时传递给形参x的值是5。若g(a)采用引用调用(callbyreference)方式传递参数,则函数f的返回值为(12);若g(a)采用值调用(callbyvalue)的方式传递参数,则函数f
在机器指令的地址字段中,直接指出操作数本身的寻址方式称为___________。
页式存储系统的逻辑地址是由页号和页内地址两部分组成。假定页面的大小为4K,地址变换过程如下图所示,图中逻辑地址用十进制表示。图中有效地址经过变换后,十进制物理地址a应为(18)。
编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段,其中,(22)并不是每种编译器都必需的。
通常测试用例很难100%覆盖测试需求,因为(47)。①输入量太大。②输出结果太多。③软件实现途径多。④测试依据没有统一标准。
以下关于模块耦合关系的叙述中,耦合程度最低的是__________(39),其耦合类型为___________(40)耦合。(40)
双层双面只读DVD盘片的存储容量可以达到(59)。
某客户端在采用ping命令检测网络连接故障时,发现可以ping通127.0.0.1及本机的IP地址,但无法ping通同一网段内其他工作正常的计算机的IP地址,说明该客户端的故障是(69)。
软件工程概念的提出是由于______。A.计算技术的发展B.软件危机的出现C.程序设计方法学的影响D.其他工程科学的影响
系统交付后,修改偶尔会出现乱码的问题,该行为属于________________维护。
随机试题
已决定不论下雨还是晴天,周五运动会照常举行。
认识的本质是【】
A.唇红B.人中点C.唇弓D.唇峰E.唇珠唇弓两侧的最高点是
心肌梗死最常发生的部位在
《中华人民共和国证券投资基金法》规定,下列事项必须通过召开基金持有人大会审议决定的是( )。
元代郭守敬所编著的《授时历》,将一年的时间确定为365.2425天。()
Thefollowingisadialogueforstudentstopractice.Canyoudistinguishwhichphonemeistheteacherguidingstudentstopract
我国的教学理论专著《学记》,出现在教学理论的形成和发展的()
为了实现功能目标,组织必须对活动过程进行规划和决策,以高效有序地完成目标任务;组织也必须对其内部的各种要素进行协调,以化解矛盾,减少内耗;组织也要对整个活动过程进行控制,以防止和纠正偏差等,这些都体现了组织的()。
某有限责任公司有股东甲、乙、丙、丁、戊5人,注册资本为200万元,其中甲、乙、丙、丁、戊分别出资10万元、20万元、10万元、10万元、150万元。公司运行3年后,效益良好,甲、乙、丙、丁在戊出差期间自行商量后通过了进一步增加注册资本50万元的决议。下列说
最新回复
(
0
)