首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,将应填入 (n) 处的字句。 [说明] 设某一机器由n个部件组成,每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量wij和价格cij。设计一个算法,求解总价格不超过上限cc的最小重量的机器组成。
阅读下列说明和C代码,将应填入 (n) 处的字句。 [说明] 设某一机器由n个部件组成,每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量wij和价格cij。设计一个算法,求解总价格不超过上限cc的最小重量的机器组成。
admin
2012-03-21
50
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
(38)属于概要设计说明书的评测内容。①分析该软件的系统结构、子系统结构,确认该软件设计是否覆盖了所有已确定的软件需求,软件每一成分是否可追溯到某一项需求。②系统定义的目标是否与用户的要求一致。③从软件维护的角度出发,确认该软件设计是否考虑了方便未来
在Internet上有许多协议,下面的选项中能正确表示协议层次关系的是(12)。
下面为C语言程序,边界值问题可以定位在(45)。 int data(3), int i, for(i=1, i<=3, i++)data(i)=100
采用________________表示带符号数据时,算术运算过程中符号位与数值位采用同样的运算规则进行处理。
(63)不属于网站渗透测试的内容。
下图是①设计模式的类图,该设计模式的目的是②,图中,Abstraction和RefinedAbstraction之间是③关系,Abstraction和Implementor之间是④关系。①处应填入?
设数组a[0..n—1,0..m一1](n>1,m>1)中的元素以行为主序存放,每个元素占用4个存储单元,则数组元素a[i,j](0≤i
软件内部/外部质量模型中,(33)不是可移植性包括的子特性。
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的权重表示活动的持续时间(天),则里程碑C在关键路径上。在其他活动按时完成的情况下,活动FJ最多可以晚_______天开始而不影响工期。
DNS服务器进行域名解析时,若采用递归方法,发送的域名请求为__________。(2011年上半年试题)
随机试题
男,75岁,查体血清PSA14.6ng/ml,MRI提示前列腺右边缘叶直径约0.3cm低回声,前列腺包膜完整。前列腺穿刺活检提示:穿刺6针,1针阳性,前列腺腺癌,该患者应采取的治疗措施为
A.HLA抗原B.甲状腺刺激性抗体(TSAb)C.独特型与抗独特型抗体D.7一干扰素E.葡萄糖激酶基因与Graves病无关的是
与体层面影像混淆的非层面的模糊投影总称为
该工程签约时的合同价款是多少万元?该工程的预付款是多少万元?
现行的《金融机构反洗钱规定》由中国人民银行制定并自()年1月1日起施行,原2003年1月3日颁布的《金融机构反洗钱规定》同时废止。
根据《保险法》的规定,保险人对保险合同中的免责条款未作提示或未明确说明的,该免责条款()。
我国旅游主管部门对导游实行的是()。
下列关于人口要素说法错误的是()。
Imaginebeingaskedtospendtwelveorsoyearsofyourlifeinasocietywhichconsistedonlyofmembersofyourownsex.Howw
基于如下两个关系:学生和专业学生(学号,姓名,专业号,年龄)
最新回复
(
0
)