首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,将应填入 (n) 处的字句。 [说明] 设某一机器由n个部件组成,每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量wij和价格cij。设计一个算法,求解总价格不超过上限cc的最小重量的机器组成。
阅读下列说明和C代码,将应填入 (n) 处的字句。 [说明] 设某一机器由n个部件组成,每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量wij和价格cij。设计一个算法,求解总价格不超过上限cc的最小重量的机器组成。
admin
2012-03-21
45
问题
阅读下列说明和C代码,将应填入 (n) 处的字句。
[说明]
设某一机器由n个部件组成,每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量wij和价格cij。设计一个算法,求解总价格不超过上限cc的最小重量的机器组成。
采用回溯法来求解该问题:
首先定义解空间。解空间由长度为n的向量组成,其中每个分量取值来自集合{1,2,…,m),将解空间用树形结构表示。
接着从根结点开始,以深度优先的方式搜索整个解空间。从根结点开始,根结点成为活结点,同时也成为当前的扩展结点。向纵深方向考虑第一个部件从第一个供应商处购买,得到一个新结点。判断当前的机器价格(c11)是否超过上限(cc),重量(w11)是否比当前已知的解(最小重量)大,若是,应回溯至最近的一个活结点;若否,则该新结点成为活结点,同时也成为当前的扩展结点,根结点不再是扩展结点。继续向纵深方向考虑第二个部件从第一个供应商处购买,得到一个新结点。同样判断当前的机器价格(c11+c21)是否超过上限(cc),重量(w11+w21)是否比当前已知的解(最小重量)大。若是,应回溯至最近的一个活结点;若否,则该新结点成为活结点,同时也成为当前的扩展结点,原来的结点不再是扩展结点。以这种方式递归地在解空间中搜索,直到找到所要求的解或者解空间中已无活结点为止。
[C代码]
下面是该算法的C语言实现。
(1)变量说明
n:机器的部件数
m:供应商数
cc:价格上限
w[][]:二维数组,w
[j]表示第j个供应商供应的第i个部件的重量
c[][]:二维数组,c
D]表示第j个供应商供应的第i个部件的价格
bestW:满足价格上限约束条件的最小机器重量
bestC:最小重量机器的价格
bestX[]:最优解,一维数组,bestX
表示第i个部件来自哪个供应商
cw:搜索过程中机器的重量
cp:搜索过程中机器的价格
x[]:搜索过程中产生的解,x
表示第i个部件来自哪个供应商
i:当前考虑的部件,从0到n-1
j:循环变量
(2)函数backtrack
int n=3;
int m=3;
int cc=4;
int w[3][3]={{1,2,3},{3,2,1},{2,2,2}};
int c[3][3]={{1,2,3},{3,2,1},{2,2,2}};
int bestW=8;
int bestC=0;
int bestX[3]={0,0,0};
int cw=0;
int cp=0;
int x[3]={0,0,0};
int backtrack (int i){
int j=0;
int found=0;
if(i>n-1){ /*得到问题解*/
bestW=cw;
bestC=cp;
for(j=0; j<n; j++){
(1) ;
}
return 1;
}
if (cp<=cc)(/*有解*/
found=1;
}
for(j=0; (2) ; j++){
/*第i个部件从第j个供应商购买*/
(3) ;
cw=cw+w
[j];
cp=cp+c
[j];
if (cp<=cc&& (4) ){/*深度搜索,扩展当前结点*/
if (backtrack(i+1)){ found -1; )
}
/*回溯*/
cw=cw - w
[j];
(5) ;
}
return found;
}
(5)
选项
答案
cp=cp-c[i][j]
解析
本题考查算法的设计和分析技术中的回溯法。
回溯法是一种系统搜索问题解的方法,在包含问题所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法在到达解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。若肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯;否则进入该子树,继续按深度优先的策略进行搜索。回溯法在求问题的最优解时,要回溯到根,且根结点的所有子树都已经被搜索遍才结束。
根据上述思想和题干说明,对实例:部件数n=3,厂商数m=3,具体的重量和价格如表4-1所示。
构造该实例的解空间树如图4-1所示。
图4-1中结点编号表示生成该结点的顺序。边上的编号表示哪个部件选择哪个厂商,如x(2)=1,表示第2个部件来自厂商1。结点旁边的两个数字表示当前解或部分解对应的重量和价格,如2:2表示重量为2,价格为2。从图4-1可以看出,最优解是结点20表示的解,即x(1)=1,x(2)=3,x(3)=1,即第1个部件来自厂商1,第2个部件来自厂商3,第3个部件来自厂商1,总的价格和重量分别为4和4。当然,本实例的最优解还可以是x(1)=1,x(2)=3,x(3)=2和x(1)=1,x(2)=3,x(3)=3,分别对应解空间树上的21号和22号结点。
代码中的空(1)处是得到问题解之后,将搜索过程中产生的重量cw、价格cp和解x放到最终重量bestW、价格bestC和解bestX中,因此空格(1)处填写bestX[j]=x[j]。空(2)处的for循环是考虑第i个部件选择哪个厂商,因此j从0到m-1依次检查,此处应填j<m。对搜索过程中产生的重量cw、价格cp和解x的值进行设置,因此空(3)处应填x
=j,表示第i个部件选择厂商j。空(4)是判断当前结点是否要扩展,若当前获得的价格比目前最优解更优,且重量没有超过当前得到的最优重量,即cp<=cc且cw<bestW,则扩展当前结点,否则回溯。在回溯过程中,需要把原来选择的部件的价格和重量从搜索过程中产生的重量cw和价格cp中去掉,因此空(5)应填cp=cp=c
[j]。
转载请注明原文地址:https://kaotiyun.com/show/HeDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
ISO/IEC9126《软件工程产品质量》统一了多种质量模型。其中,下述关于软件使用质量的描述,不正确的是______。A.它测量用户在特定环境中能达到其目标的程度,不是测量软件自身的属性B.使用质量的属性分为4个特性:有效性、生产率、安全性和满意度
以下说法不正确的选项包括(48)。①软件测试不仅仅指测试的执行,还包括很多其他的活动②软件测试是一个独立的流程,贯穿产品整个生命周期,与其他流程并发地进行③应用H模型有利于资源调配,有助于跟踪测试投入的流向④H模型指
对于逻辑表达式((a||b)||(c&&d)),需要()个测试用例才能完成条件组合覆盖。
(41)不是易用性测试包括的内容。
下面为C语言程序,边界值问题可以定位在(45)。 int data(3), int i, for(i=1, i<=3, i++)data(i)=100
在软件开发过程中,常采用图形表示相关的信息,(28)不用于表示软件模块的执行过程。
对于逻辑表达式(bufc[i]>223&&bufc[i]<240&&i+2<totalbytes),需要______个测试用例才能完成条件组合覆盖。
以下不属于在需求分析阶段编写的文档是
阅读以下说明,回答问题1至问题4,将解答填人答题纸的对应栏内。[说明]某小公司的网络拓扑如图9-2所示。其中路由器具有ISDN模块,公司网络通过ISDN连接到ISP。
造成故障1的原因是什么?如何解决?1.将故障2中(1)和(2)两处合适的答案填入答题纸相应的解答栏内。2.故障2如何解决?
随机试题
牛奶中碳水化合物的存在形式为
A.气瘿B.血瘿C.筋瘿D.肉瘿E.石瘿以山区、高原地区的青春期、怀孕期及哺乳期的妇女多见的疾病是()
肠外营养静脉导管的护理,以下不正确的是
某建筑公司的司机将自己所驾驶的该建筑公司运送沥青混凝土的运输车开进了施工现场附近的一条小河里进行清洗,该行为属于()。
《证券法》规定,单位操纵证券市场的,应对直接负责的主管人员和其他直接责任人员给予警告,并处10万元以上( )万元以下的罚款。
皮亚杰认为5~10岁之间的儿童出现的道德性一般是()。
根据以下资料,回答问题2008年1—9月,全省高新技术产业中各行业产值增长额最多的是()。
被誉为“欧洲古代教育理论发展最高成就”的是()。(2015·辽宁)
( )公安机关均设立督察机构。
A.probablyB.plantC.reasoningD.abilityE.stageF.speciesG.mammalH.differI.prehistoricJ.periodK.contact
最新回复
(
0
)