最小重量机器设计问题、工作分配问题

最小重量机器设计问题1。

问题描述设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。

设wij是从供应商j处购得的部件i的重量，cij是相应的价格。

试设计一个算法，给出总价格不超过c的最小重量机器设计.算法设计:对于给定的机器部件重量和机器部件价格，计算总价格不超过d的最小重量机器设计。

2.算法流程分析设开始时bestx=［-1,—1,…,—1]则相应的排列树由x[0：n—1]的所有排列构成。

找最小重量机器设计的回溯算法Backtrack是类machine的公有成员。

私有数据成员整型数组Savex保存搜索过的路径，到达叶节点后将数据赋值给数组bestx。

成员bestw记录当前最小重量,cc表示当前花费，cw表示当前的重量。

在递归函数Backtrack中，在保证总花费不超过c的情况下：当i=n时，当前扩展结点是排列树的叶节点。

此时搜索到一个解，判断此时的最小重量是否小于当前最小重量,若小于则更新bestw, 并得到搜索路径bestx.当i〈n时，当前扩展结点位于排列树的第i—1层.当x[0:i]的花费小于给定最小花费时,算法进入排列树的第i层,否则将减去相应的子树。

算法用变量cc记录当前路径x[0：i］的费用。

3。

算法正确性证明通过几组实例证明合法的输入可以得到正确的输出.实例见附录第2部分。

4.算法复杂度分析时间复杂度是O（n2）5.参考文献［1] 王晓东编著，计算机算法设计与分析(第4版）。

北京：电子工业出版社，2012。

26。

附录（1）可执行代码如下:#include<iostream〉using namespace std；＃define N 50class MinWmechine｛int n; //部件个数int m；//供应商个数int COST; //题目中的Cint cw; //当前的重量int cc；//当前花费int bestw; //当前最小重量int bestx［N］;int savex［N］;int w[N]［N］；int c[N］[N];public:MinWmechine(）;void machine_plan（int i）;void prinout（）;};MinWmechine：:MinWmechine（）｛cw=0; //当前的重量cc=0; //当前花费bestw=-1；//当前最小重量bestx[N];savex[N］；cout<<”请输入部件个数："；cin〉〉n；cout〈〈”请输入供应商个数："; cin>〉m；cout<<”请输入总价格不超过："; cin>〉COST；for(int j=0;j<m；j++){for（int i=0;i〈n；i++）cout〈〈"请输入第"〈〈j+1〈<" 个供应商的第"〈〈i+1<〈”个部件的重量：”;cin>>w[i]［j];cout〈〈”请输入第”〈<j+1〈<”个供应商的第”〈<i+1<<”个部件的价格：";cin〉>c［i]［j]；if（w［i][j]〈0 ｜｜c[i][j]<0）｛cout〈<"重量或价钱不能为负数!\n";i=i—1；}}｝}void MinWmechine::machine_plan(int i)｛if（i>=n)｛if(cw 〈bestw ｜| bestw==—1）{bestw=cw；for（int j=0;j〈n; j++) //把当前搜过的路径记下来savex［j]=bestx[j］；return；}for(int j=0; j<m; j++）//依次递归尝试每个供应商｛if（cc+c［i]［j］〈COST）{cc+=c［i][j];cw+=w［i][j];bestx［i]=j；machine_plan（i+1)；bestx[i]=-1；cc-=c［i]［j]；cw—=w[i］［j];｝｝｝void MinWmechine：:prinout（)｛int i，j，ccc=0;for（j=0;j〈m;j++）{for(i=0;i〈n；i++)｛cout<〈"第”<<j+1〈<”供应商的第”<〈i+1〈〈”部件重量：”<〈w［i］［j]〈〈" 价格："<〈c[i］[j]<<"\n”;}｝for(j=0; j<n; j++){bestx[j］=-1;｝machine_plan(0);cout<<”\n最小重量机器的重量是："〈<bestw〈〈endl；for(int k=0；k〈n；k++）{cout<<" 第"〈〈k+1〈〈" 部件来自供应商”〈<savex［k]+1<〈"\n”;ccc+=c［k］［savex[k］]；｝cout〈〈"\n该机器的总价钱是: "<〈ccc<<endl;cout〈<endl；｝int main（void)｛MinWmechine Y；Y。

任务分配到机床摘要本文解决的是在不同加工要求下，机床加工过程中的任务分配问题，属于组合优化问题。

为解决此问题，我们运用数学中的约束规划与整数规划的混合方法[1] ，建立起最优化模型。

针对问题一：本文首先根据机床工作时间定义机床任务量均衡度，均衡度越小，各机床任务量越均衡。

由于不同产品加工任务量、可用机床不同，本文将整数规划作为主问题解决机器的分派问题，将约束规划作为子问题解决任务在机床上加工的排序问题。

然后确立两个目标函数：最短完成订单时间，最小均衡度。

最后根据确立的这两个目标建立起双目标最优化模型，运用lingo软件编程得到完成订单的最短时间为270小时，机床任务量均衡度为1.4%，各机床任务分配见5.3表二，各机床完成加工时间如下表：机床1机床2机床3机床4机床5机床6 230小时259小时231小时231小时267小时270小时针对问题二：本文在解决问题一的基础上，将机床的加工时间作为变量1，将产品在机床间的调度次数作为变量2，并以机床运行费用和调度费用确立的总生产费为目标函数，建立起单目标最优化模型，运用lingo软件编程得到最小总生产费用为202.75万元，各机床任务分配见6.3表四，各机床加工费用和调度总费用如下表：机床机床1 机床2 机床3 机床4 机床5 机床6 调度费用总费用费用（万）45.4 41.58 34.65 27.72 23 18.4 12 202.75 最后我们针对实际情况，对模型进行了改进，改进后的整数规划与约束规划模型使机床加工调度问题更接近实际，此时得出的分配方案更优。

关键字：约束规划整数规划车间作业调度一问题重述1.1问题背景在制造企业的中期或短期生产计划管理中，常常要考虑到如下的生产计划优化问题：在给定的外部需求和生产能力等限制条件下，按照一定的生产目标（生产总时间最小、生产总费用最小）编制未来若干个生产周期的最优生产计划。

1.2该工厂机床加工各种产品相关信息某工厂收到了5个客户提交的5种不同的加工任务订单,5个客户的任务订单量分别为 8,13,7,12，5。

最小重量机器设计问题1．问题描述<1>.问题设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。

设Wij 是从供应商j处购得的部件i的重量，Cij 是相应的价格。

试设计一个算法，给出总价格不超过c的最小重量机器设计。

算法设计：对于给定的机器部件重量和机器部件价格，计算总价格不超过d的最小重量机器设计。

<2>.数据输入：由文件input.txt给出输入数据。

第一行有 3 个正整数 n ，m和 d。

接下来的2n 行，每行m个数。

前n行是c，后n行是w。

<3>.结果输出：将计算出的最小重量，以及每个部件的供应商输出output.txt Input.txt output.txt3 34 41 2 3 1 3 13 2 12 2 21 2 33 2 12 2 2<4>.算法设计：回溯算法中的递归回溯我采用的是子集树表示其解空间树。

cc表示当前所购买的机器总费用，在第i+1层的结点Z处，用cc记当前费用，若不满足cc<=cm，则以结点Z为根的子树中所有结点都不满足约束条件，因而该子树的解均为不可行解，可剪掉该子树。

MinSupply函数返回满足要求的最小机器重量。

Backtrack（i）搜索第i层子树，j=1,2,…m表示由1,2，…m供应商提供,bestx记录当前最优解。

当i<=n 时，当前扩展结点Z是子集树中的内部结点。

该结点有x[i]=1,2,3…m共m个子树，仅当cc+c[i][j]<=cm时进入x[i]=j的子树。

构成的解空间树如下：部件1：部件2：部件3：2.程序代码Supply.hclass Supply{public:friend int MinSupply(int **W,int **C,int m,int n,int d,int bestx[]); private:void Backtrack(int i);int n,//n个部件m,//m个供应商*x,//当前解*bestx,//当前最优解**w,//不同提供商提供不同部件的重量**c,//不同提供商提供不同部件的重量cw,//当前已选部件的总重量bestw,//当前最小载重量cm,//价格上限cc;//当前价格};Supply.cpp#include"Supply.h"void Supply::Backtrack(int i) {int j;//搜索第i层结点if(i>n){//到达叶结点if(bestw==0)bestw=cw;elseif(cw<bestw){for(i=1;i<=n;i++)bestx[i]=x[i];bestw=cw;}return;}//搜索子树for(j=1;j<=m;j++){if(cc+c[i][j]<=cm){x[i]=j;cw+=w[i][j];Backtrack(i+1);//搜索下一层结点cw-=w[i][j];//返回上一层结点时的操作}}}int MinSupply(int **W,int **C,int m,int n,int d,int bestx[]) {//返回最优载重量Supply X;//初始化XX.x=new int [n+1];//存n个部件分别取自的供应商X.w=W;X.c=C;X.n=n;X.m=m;X.cm=d;X.bestx=bestx;X.bestw=0;X.cw=0;X.Backtrack(1);delete []X.x;return X.bestw;}Main.cpp#include<iostream.h>#include<fstream.h>#include"Supply.h"void main(){ifstream in("input.txt");//定义读取文件if(in.fail()){cout<<"error file!"<<endl;return;}int weight[10][10],cost[10][10],n,m,d,bestx[10],i,j,Minw;int*p[10]={weight[0],weight[1],weight[2],weight[3],weight[4], weight[5],weight[6],weight[7],weight[8],weight[9]};int*q[10]={cost[0],cost[1],cost[2],cost[3],cost[4],cost[5],cost[6],cost[7],cost[8],cost[9]};in>>n>>m>>d;for(i=1;i<=n;i++)for(j=1;j<=m;j++)in>>cost[i][j];for(i=1;i<=n;i++)for(j=1;j<=m;j++)in>>weight[i][j];for(i=1;i<=n;i++)bestx[i]=0;Minw=MinSupply(p,q,m,n,d,bestx);ofstream out("output.txt");//定义输出文件out<<Minw<<'\n';cout<<Minw<<'\n';for(i=1;i<=n;i++){cout<<bestx[i]<<' ';out<<bestx[i]<<' '; }cout<<endl;}。

最⼩重量机器设计问题问题描述：设某⼀机器由n个部件组成，每⼀种部件都可以从m个不同的供应商处购得。

设wij是从供应商j处够来的部件i的重量，cij是相应的价格。

试设计⼀个算法，给出总价格不超过c的最⼩重量机器设计。

算法设计：对于给定的机器部件重量和机器部件价格，计算总价值不超过d的最⼩重量机器设计。

数据输⼊：第⼀⾏由3个正整数n，m，d。

接下来的2n⾏，每⾏m个数。

前n⾏是c，后n⾏是w。

结果输出:将计算的最⼩重量及每个部件的供应商输出。

输⼊：3 3 41 2 33 2 12 2 21 2 33 2 12 2 2输出：41 3 12、解题思路：由于题⽬已经给出总价格的上限，因此算法通过使⽤回溯来选择合适的机器使得在总价格不超过d时得到的机器重量最⼩。

⾸先初始化当前价格cp=0,当前重量cw=0,此外，还要设置⼀个变量bestw表⽰选择机器的总重量，初始化其为每个部件从1号供应商购买的重量。

在循环选择i号机器时，判断从j号供应商购买机器后的价格是否⼤于总价格，如果不⼤于则选择，否则不选，继续选择下⼀供应商进⾏判断。

在得到⼀个合适的供应商后，继续选择下⼀机器的供应商，从第⼀个选到最后⼀个供应商。

当所有机器选择结束后，判断得到的总重量是否⽐之前的bestw⼩，如果⼩就赋给bestw，然后从这⼀步开始，回溯到上⼀机器，选择下⼀合适供应商，继续搜索可⾏解，直到将整个排列树搜索完毕。

这样，最终得到的bestw即为最优解。

当然，考虑到算法的时间复杂度，还可以加上⼀个剪枝条件，即在每次选择某⼀机器时，再判断选择后的当前重量是否已经⼤于之前的bestw，如果⼤于就没必要继续搜索了，因为得到的肯定不是最优解。

3、算法设计：a.部件有n个，供应商有m个，分别⽤array2[i][j]和array1[i][j]存储从供应商j 处购得的部件i的重量和相应价格，d为总价格的上限。

b.⽤递归函数machine(i)来实现回溯法搜索排列树（形式参数i表⽰递归深度）。

《算法设计》课程报告课题名称：算法设计课题负责人名（学号）： ---同组成员名单（角色）： ---指导教师： ---评阅成绩：评阅意见：提交报告时间：2014年 6 月 17 日最小重量机器设计问题计算机科学与技术专业学生 -- 指导老师 ---[题目描述] 设某一机器由 n 个部件组成，每一种部件都可以从m 个不同的供应商处购得。

高 wij 是从供应商 j 处购得的部件 i 的重量，cij 是相应的价格。

试设计一个算法，给出总价格不超过 c 的最小重量机器设计。

编程任务：对于给定的机器部件重量和机器部件价格，编程计算总价格不超过 d 的最小重量机器设计。

数据输入：由文件 input.txt 给出输入数据。

第一行有 3 个正整数 n，m 和 d。

接正业的 2n 行，每行 n 个数。

前 n 行是 c，后 n 行是 w。

结果输出：将计算出的最小重量，以及每个部件的供应商输出到文件output.txt。

输入文件示例输出文件示例input.txt output.txt3 34 41 2 3 1 3 13 2 12 2 2 1 23 3 2 1 2 2 2[算法分析]采用回溯算法和分支定界法分别实现，对于回溯法，采用深度优先搜索对子集树进行剪枝，剪枝条件是当前的总费用不超过总费用；对于分支定界法，采用按照层次遍历对子集树进行剪枝，并将每层的结点按照重量由小到大进行排序，将相应下标保存在二维数组s中，以便构造最优解。

两种算法是时间复杂度都是O(m^n) ，空间复杂度均为O(nm)，但由于分支定界法在已经排好序的序列中查找，因此查找到的第一个解即为最优解，理论上来说，时间效率会比回溯法高。

[程序实现]回溯法代码#include <iostream>#include <stdlib.h>#include <fstream>#include <vector>#include <stdio.h>#include <string.h>using namespace std;#define INF 999999999#define MAXSIZE 100+1int cur_solution[MAXSIZE];int solution[MAXSIZE];int w[MAXSIZE][MAXSIZE]; //weightint c[MAXSIZE][MAXSIZE]; //costint minWeight;int cur_minWeight;void Backtrack(int t,int n,int m,int d){if(t>n){if(cur_minWeight < minWeight){//保存最优解和最优值minWeight = cur_minWeight;for(int r=1;r<=n;++r){solution[r] = cur_solution[r];}}}else{for(int i=1;i<=m;++i){d -= c[t][i];cur_solution[t] = i;cur_minWeight += w[t][i];if(d>=0) {Backtrack(t+1,n,m,d);}cur_minWeight -= w[t][i];//if(Constraint(t) && Bound(t)) Backtrack(t+1,n,m,d);d += c[t][i];}}return;}int main(){int n,m,d;cout<<"Please input the input file path:"<<endl;char strPath[63];while(scanf("%s",strPath)==1){ifstream fin(strPath);cout<<"Please input the output file path:"<<endl;cin>>strPath;ofstream fout(strPath);if(fin.good() && fout.good()){minWeight = INF;cur_minWeight = 0;fin>>n>>m>>d;int j,k;for(j=1;j<=n;++j){for(k=1;k<=m;++k){fin>>c[j][k];}}for(j=1;j<=n;++j){for(k=1;k<=m;++k){fin>>w[j][k];}}Backtrack(1,n,m,d);fout<<minWeight<<endl;for(int r=1;r<=n;++r){fout<<solution[r]<<" ";}fout<<endl;fout.close();fin.close();}else{cout<<"Open file error!"<<endl;exit(0);}cout<<endl<<endl<<"Please input the input file path:"<<endl;}return 0;}分支定界法代码#include <stdio.h>#include <stdlib.h>#include <list>#include <iostream>using namespace std;#define MAX_NODE 256typedef struct _node{int weight,price;int level,th;struct _node *prev;}node;void qs(int *a,int *s,int b,int e)//快速排序{int t,c=a[s[b]];int l=b,r=e;while(l<r){while(l<r&&a[s[r]]>=c)--r; t=s[r];s[r]=s[l];s[l]=t;while(l<r&&a[s[l]]<c)++l; t=s[r];s[r]=s[l];s[l]=t;}if(b<l)qs(a,s,b,l-1);if(l<e)qs(a,s,l+1,e);}int main(){int *w=0,*p=0,n,m,c,i,j;int *minprice;int level,price,weight;list<node*> que;list<node*>::iterator it;node *pnode;/* 读取文件 */FILE *pf;if((pf=fopen("input.txt","r"))!=0){fscanf(pf,"%d%d%d",&n,&m,&c);w=(int *)malloc(n*m*sizeof(int));//重量p=(int *)malloc(n*m*sizeof(int));//价格for(i=0;i<n;++i)for(j=0;j<m;++j)fscanf(pf,"%d",w+i*m+j);for(i=0;i<n;++i)for(j=0;j<m;++j)fscanf(pf,"%d",p+i*m+j);fclose(pf);}else{printf("no input file!!\n");getchar();exit(0);}/* 准备数据 */int s[n][m]; //用来为每一种零件的质量排序，for(i=0;i<n;++i)for(j=0;j<m;++j)s[i][j]=j;minprice=(int*)malloc((n+1)*sizeof(int));//用来记录买了i个零件后，买完剩下的零件至少还要多少钱minprice[n]=0; //买了n个零件之后，不需要再买了for(i=0;i<n;++i){minprice[i]=p[i*m];for(j=1;j<m;++j) //找出买第i个零件的最低价格{minprice[i]=minprice[i]<p[i*m+j]?minprice[i]:p[i* m+j];}}for(i=n-2;i>=0;--i) //计算买剩下的零件至少要多少钱{minprice[i]=minprice[i+1]+minprice[i];}for(i=0;i<n;++i) //每种零件按重量排序，排序下标记录的s中,排序后w[i*m+s[i][j]]，i相同时，对于变量j是递增的qs(w+i*m,s[i],0,m-1);/* 开始计算 */for(i=0;i<m;++i) //初始数据把第一种零件的所有情况放入活结点队列{pnode=new node;pnode->weight=w[s[0][i]];pnode->price=p[s[0][i]];if(pnode->price+minprice[2]<=c){pnode->th=i;pnode->level=1;pnode->prev =0;que.push_back(pnode);}else delete pnode;}while(!que.empty()) //计算，直到得出结果或者队列为空{level =que.front()->level;price =que.front()->price;weight=que.front()->weight;if(level<n)for(i=0;i<m;++i) //如果队首不为叶子结点，扩展队首结点{pnode=new node;pnode->weight=weight+w[level*m+s[level][i]];pnode->price=price+p[level*m+s[level][i]];if(pnode->price+minprice[level+1]<=c) //剪枝，如果当前结点剩下的钱不够买全所有零件，则剪掉{pnode->th=s[level][i];pnode->level=level+1;pnode->prev =que.front();for(it=que.begin();it!=que.end();++it) //按重量递增构造优先队列if(pnode->weight<(*it)->weight)break;que.insert(it,pnode);if(level==n-1)break; //如果已经找到答案，退出循环}else delete pnode;}que.pop_front();if(i<m)break; //如果已经找到答案，退出循环}/* 输出答案 */if(pnode->level!=n){printf("can not find answer!!");getchar();exit(0);}pf=fopen("output.txt","w");if(pf){fprintf(pf,"%d\n",pnode->weight);int count=n,ans[n];while(pnode){ans[--count]=pnode->th;pnode=pnode->prev;}for(i=0;i<n;++i)fprintf(pf,"%d ",ans[i]);fputc('\n',pf);fclose(pf);}if(minprice)free(minprice);if(w)free(w);if(p)free(p);return 0;}[运行结果]回溯法运行结果如下，分支定界法结果与下列一致，读者可以自行运行比对参考文献[1] 王晓东.计算机算法设计与分析.--3版.--北京：电子工业出版社2007.5。

案例4 机器负荷分配问题案例4 机器负荷分配问题某机器可以在高、低两种不同的负荷下进行生产。

高负荷下生产时，产品年产量s1?8u1，式中u1为投入生产的机器数量，机器的年折损率为a?07.，即年初完好的机器数量为u1，年终就只剩下0.7u1台是完好的，其余均需维修或报废。

在低负荷下生产，产品年产量s2?5u2，式中u2为投入生产的机器数量，机器的年折损率为x1?1000台，要求制定一个五年计划，在每年开始时决定如何重新分配好机器在两种不同负荷下工作的数量，使产品五年的总产量最高。

模型分析设阶段变量k表示年度，状态变量xk是第k年初拥有的完好机器数量。

k?0时它也是k?1年度末的完好机器数量，决策变量xk规定为第k年度中分配在高负荷下生产的机器数量。

于是xk?uk是该年度分配在低负荷下生产的机器数量。

这里与前面几个例子不同的是xk，uk的非整数值可以这样来理解：例如xk=0.6 表示一台机器在该年度正常工作时间只占60%；uk=0.3 表示一台机器在该年度的3/10时间里在高负荷下工作。

此时状态转移方程为xk?1?0.7uk?0.9(xk?uk),k?1,2,?,5k阶段的允许决策集合是Dk(xk)?{uk|0?uk?xk}第k年度产品产量是vk( xk,uk)?8uk?5(xk-uk) 指数函数是Vk?[8uj?k5j?5(xj?uj)]最优值函数为fk(xk)?第k年初从xk出发到第5年度结束产品产量的最大值由最优化原理得递推关系为 fk(xk)?max{8uk?5(xk?uk)?fk?1[0.7uk?0.9(xk?uk)]}uk?Dk(xk)边界条件是f6(x6)?0，计算过程如下：k?5时，f5(x5)?max{8u5?5(x5?u5)?f6[0.7u5?0.9(x5?u5)]}0?u5?x5 ?max{8u5?5(x5?u5)}0?u5?x5 ?max{3u5?5x5}0?u5?x5因为f5的表示式是u5的单调函数，所以最优决策u5=x5，f5(x5)=8x5；*k?4时,{8u4?5(x4?u4)?f5[0.7u4?0.9(x4?u4)]}f4(x4)?max0?u4?x4?max{8u4?5(x4?u4)?8[0.7u4?0.9(x4?u4)]}0?u4?x4.u4?12.2x4} ?max{140?u4?x4同理，最优决策 u4=x4，f4(x4)=13.6x4，依次可以 u3?x3,u2?0,****f3(x3)=17.6x3 f2(x2)=20.8x2u1?0,f1(x1)=23.7x1因为x1=1000，所以f1(x1)=23700（台）。

第十三章习题1、栈式分支限界法将活结点表以后进先出(LIFO)的方式存储于一栈中．试设计一个解0-1背包问题的栈式分支限界法，并说明栈式分支限界法与回溯法的区别。

2、试修改解装载问题和解0-1背包问题的优先队列式分支限界法，使其仅使用一个最大堆来存储活结点，而不必存储所产生的的解空间树。

3、试修改解旅行售货员问题的分支限界法，使得s = n-2的结点不插入优先队列，而是将当前最优排列存储于bestp中．经这样修改后，算法在下一个扩展结点满足条件Lcost>=bestc 时结束。

4、试设计解电路板排列问题的队列式分支限界法，并使算法在运行结束时输出最优解和最优值。

5、只使用一个最大优先队列，利用最大收益分支定界法求解0/1背包问题，即不必保存一个部分解空间树，所有优先队列中的节点都记录着通往根结点的路径。

6、试修改解装载问题和解0-1背包问题的优先队列式分支限界法，使得算法在运行结束时释放所有类型为bbnode和HeapNode的结点所占用的空间。

7、试修改解旅行售货员问题的分支限界法，使得算法保存已产生的排列树。

8、试设计解电路板排列问题的队列式分支限界法，并使算法在运行结束时输出最优解和最优值。

9、设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。

设w ij是从供应商j处购得的部件i的重量，c ij是相应的价格。

设计一个优先队列式分支限界法，给出总价格不超过d的最小重量机器设计。

10、世界名画陈列馆由m*n个排列成矩形阵列的陈列室组成。

为了防止名画被盗，需要在陈列室中设置警卫机器人哨位。

每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在的陈列室相邻的上、下、左、右4个陈列室。

试设计一个安排警卫机器人哨位的优先队列分支限界算法，使名画陈列馆中每一个陈列室都在警卫机器人的监视之下，且所用的警卫机器人数最少。

11、给定n个正整数和4个运算符+、-、*、/，且运算符无优先级，如2+3*5=25.对于任意给定的整数m，试设计一个优先队列分支限界算法，用以上给出的n个数和4个运算符，产生整数m，且用的运算次数最少。

堆石子游戏的问题（多元Huffman编码）问题描述：在一个操场的四周摆放着n 堆石子。

现要将石子有次序地合并成一堆。

规定每次至少选2 堆最多选k堆石子合并成新的一堆，合并的费用为新的一堆的石子数。

试设计一个算法，计算出将n堆石子合并成一堆的最大总费用和最小总费用。

编程任务：对于给定n堆石子,编程计算合并成一堆的最大总费用和最小总费用。

Input测试数据的第1 行有2个正整数n和k，表示有n堆石子，每次至少选2堆最多选k堆石子合并。

第2行有n个数，分别表示每堆石子的个数。

Output输出最大总费用和最小总费用，用一空格隔开，每个答案一行。

Sample Input7 345 13 12 16 9 5 22Sample Output593 199代码：#include<iostream>#include<algorithm>#include<vector>using namespace std;bool cmp(int a, int b){return a>b;}void Insert(vector<int> &f, int pos, int value) {for (int i = () - 1; i > pos; i--){f[i] = f[i - 1];}f[pos] = value;}int Find(vector<int> f, int value){int pos = () - 1;while (pos >= 0 && f[pos] < value){pos--;}return pos + 1;}int MaxNum(vector<int> f){sort(), ());int Max;Max = 0;while () >= 2){int sum = f[() - 1] + f[() - 2];Max = Max + sum;() - 1);f[() - 1] = sum;}return Max;}int MinNum(vector<int> f, int len){sort(), (), cmp);int Min;Min = 0;while () >= len){int sum = 0;for (int i = () - 1; i >= () - len && i >= 0; i--){sum = sum + f[i];}Min = Min + sum;() - len + 1);if () > len){int pos = Find(f, sum);Insert(f, pos, sum);}else if () != 1){f[() - 1] = sum;for (int i = 0; i < (); i++){Min = Min + f[i];}break;}else{break;}}return Min;}bool run(){int n, m;if (!(cin >> n >> m)) return false;vector<int> f(n);for (int i = 0; i < n; i++){cin >> f[i];}int Max, Min;Max = MaxNum(f);while () % (m - 1) != 1){(0);}Min = MinNum(f, m);cout << Max << " " << Min << endl;return true;}int main(){while (run());return 0;}——————————————————————————————————————————————————登山机器人问题问题描述：登山机器人是一个极富挑战性的高技术密集型科学研究项目，它为研究发展多智能体系统和多机器人之间的合作与对抗提供了生动的研究模型。