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

admin2012-03-21  36

问题 阅读下列说明和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;
   }

(4)

选项

答案cw<bestW

解析
转载请注明原文地址:https://jikaoti.com/ti/Kui7FFFM
0

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