2. 计算机
  3. 阅读下列说明和C代码，将应填入 (n) 处的字句。 [说明] 设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量wij和价格cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。

阅读下列说明和C代码，将应填入 (n) 处的字句。 [说明] 设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量wij和价格cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。

admin2012-03-21  39
问题 阅读下列说明和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[][]：二维数组，cD]表示第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;
   }

(3)
选项
答案x[i]=j
解析
转载请注明原文地址:https://kaotiyun.com/show/WeDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)