最小重量机器设计问的题目.docx
- 文档编号:15866378
- 上传时间:2023-07-08
- 格式:DOCX
- 页数:21
- 大小:21.26KB
最小重量机器设计问的题目.docx
《最小重量机器设计问的题目.docx》由会员分享,可在线阅读,更多相关《最小重量机器设计问的题目.docx(21页珍藏版)》请在冰点文库上搜索。
最小重量机器设计问的题目
最小重量机器设计问题
(1)部件有n个,供应商有m个,分别用c[i][j]和w[i][j]存储从供应商j 处购得的部件i的价格和相应重量,d为总价格的上限,savex[i]存储第i个部件的的供应商。
(2)用递归函数backtrack(i)来实现回溯法搜索排列树(形式参数i表示递归深度)。
① 若cp>d,则为不可行解,剪去相应子树,返回到i-1层继续执行。
② 若cw>=weight,则不是最优解,剪去相应子树,返回到i-1层继续执行。
③ 若i>n,则算法搜索到一个叶结点,用weight对最优解进行记录,返回到i-1层继续执行;
④ 用for循环对部件i从m个不同的供应商购得的情况进行选择(1≤j≤m)。
(3)主函数调用一次backtrack
(1)即可完成整个回溯搜索过程,最终得到的weight即为所求最小总重量,p为该机器最小重量的价格。
代码及结果
#include"stdafx.h"
#include
usingnamespacestd;
#defineN50
classMinWmechine
{
intn;//部件个数
intm;//供应商个数
intCOST;//题目中的C
intcw;//当前的重量
intcc;//当前花费
intbestw;//当前最小重量
intbestx[N];
intsavex[N];
intw[N][N];
intc[N][N];
public:
MinWmechine();
voidmachine_plan(inti);
voidprinout();
};
MinWmechine:
:
MinWmechine()
{
cw=0;//当前的重量
cc=0;//当前花费
bestw=-1;//当前最小重量
bestx[N];
savex[N];
cout<<"请输入部件个数:
";
cin>>n;
cout<<"请输入供应商个数:
";
cin>>m;
cout<<"请输入总价格不超过:
";
cin>>COST;
for(intj=0;j { for(inti=0;i { cout<<"请输入第"< "; cin>>w[i][j]; cout<<"请输入第"< "; cin>>c[i][j]; if(w[i][j]<0||c[i][j]<0) { cout<<"重量或价钱不能为负数! \n"; i=i-1; } } } } voidMinWmechine: : machine_plan(inti) { if(i>=n) { if(cw { bestw=cw; for(intj=0;j savex[j]=bestx[j]; } return; } for(intj=0;j { if(cc+c[i][j] { 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]; } } } voidMinWmechine: : prinout() { inti,j,ccc=0; for(j=0;j { for(i=0;i { cout<<"第"< "< "< } } for(j=0;j { bestx[j]=-1; } machine_plan(0); cout<<"\n最小重量机器的重量是: "< for(intk=0;k { cout<<"第"< ccc+=c[k][savex[k]]; } cout<<"\n该机器的总价钱是: "< cout< } intmain(void) { MinWmechineY; Y.prinout(); return0; } 矩阵连乘问题 【问题】: 矩阵链乘问题: 给定n个矩阵{A1,A2,...,An},其中Ai与Ai+1是可乘的,i=1,2...,n-1。 如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。 【解题】: 这里我采用的是动态划分算法: 设计动态规划算法的步骤。 (1)找出最优解的性质,并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息,构造最优解(由子结构的最优解得到原先大问题的最优解)。 【解题关键】: 将一系列相乘的矩阵(Ai....Aj)划分为两部分;即(AiAi+1...Ak)(Ak+1Ak+2....Aj),k的位置要保证左边括号和右边括号相乘的消耗最小。 【思路】: 这里我采用两种方法来实现: (1)用三重for循环来实现: 根据主对角线的方向及其右边与之平行的对角线方向,由上至下,从左到右分别求出C[i][j]的值,后面要求的值都可以根据前面所求的的值来求。 C[i][j]代表矩阵链Ai..Aj相乘的最小消耗。 其中: c[i][i]=0,i=1,2,....n 求解的顺序如下: C[1][2],C[2][3],C[2][3],...,C[N-1][N],C[1][3],C[2][4]....C[N-2][N]..........C[N][N] 最后得到的C[N][N]的值就是我们所求的。 (2)备忘录方法(即递归算法): 将整个矩阵链分成两部分,然后在分别对两边的子矩阵链递归调用算法。 【程序代码】: 两种方法都在其中: #include #include #include #include #defineMAX_VALUE100 #defineN201//连乘矩阵的个数(n-1) #definerandom()rand()%MAX_VALUE //控制矩阵的行和列的大小 intc[N][N],s[N][N],p[N]; intmatrixchain(intn) //3个for循环实现 { for(intk=1;k<=n;k++) c[k][k]=0; for(intd=1;d for(inti=1;i<=n-d;i++) { intj=i+d; c[i][j]=INT_MAX; for(intm=i;m { intt=c[i][m]+c[m+1][j]+p[i-1]*p[m]*p[j]; if(t { c[i][j]=t; s[i][j]=m; } } } returnc[1][n]; } voidPrint(ints[][N],inti,intj)// 输出矩阵连乘积的计算次序 { if(i==j) cout<<"A"< else { cout<<"("; Print(s,i,s[i][j]); //左半部子矩阵连乘 Print(s,s[i][j]+1,j); //左半部子矩阵连乘 cout<<")"; } } intlookupchain(inti,intj) //备忘录方法 { if(c[i][j]>0) returnc[i][j]; if(i==j) return0; intu=lookupchain(i,i)+lookupchain(i+1,j)+p[i-1]*p[i]*p[j]; s[i][j]=i; for(intk=i+1;k { intt=lookupchain(i,k)+lookupchain(k+1,j)+p[i-1]*p[k]*p[j]; if(t { u=t; s[i][j]=k; } } c[i][j]=u; returnu; } voidmain() { srand((int)time(NULL)); for(inti=0;i 1~MAX_VALUE p[i]=random()+1; clock_tstart,end; doubleelapsed; start=clock(); //cout<<"Count: "< cout<<"Count: "< end=clock(); elapsed=((double)(end-start));///CLOCKS_PER_SEC; cout<<"Time: "< Print(s,1,N-1); //输出矩阵连乘积的计算次序 cout< } 【总结】: 两种算法的时间复杂度均为o(n3),,随着数据量的增多,备忘录方法消耗的时间越长;我觉得是由于递归算法,随着数据量增大,调用函数的次数也增大,语句被执行的时间也越多,因此调用函数消耗的时间也增多。 最优服务次序问题 平均等待时间是n个顾客等待服务时间的总和除以n。 假设n个顾客等待时间的总和为T,已知每个客户各自单独所需的服务时间序列为t={t1,t2,…,tn}(其中ti为第i个用户需要的服务时间),则每个用户等待时问Ti为: T1=t1;T2=t1+t2;Tn=t1+t2+…+tn;总时间就是T=T1+T2+…+Tn,平均等待时间就是T/n 四、算法描述及复杂度分析 #include #include #include #include #include usingnamespacestd; intx[10000]; intmain() { intn; cout<<"请输入顾客的人数n: "; cin>>n; inttemp; for(intj=0;j { printf("请输入第%d个顾客的服务时间: ",j+1); scanf("%d",&x[j]); } sort(x,x+n); for(inti=1;i x[i]+=x[i-1]; doublet=0; for(i=0;i t+=x[i]; t/=n; cout.setf(ios: : fixed); printf("最小平均等待时间: "); cout< (2)< system("pause"); return0; } 连续邮资问题问题描述: 假设国家发行了n种不同面值的邮票,并且规定每张信封上最多只允许贴m张邮票。 连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计,在1张信封上可贴出从邮资1开始,增量为1的最大连续邮资区间。 例如,当n=5和m=4时,面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。 问题分析: 如果使用动态规划方法计算数组y的值,状态转移过程: 将x[i-1]加入等价类集S中,将会引起数组x能贴出的邮资范围变大,对S的影响是如果S中的邮票不满m张,那就一直贴x[i-1],直到S中有m张邮票,这个过程会产生很多不同的邮资,取能产生最多不同邮资的用邮票最少的那个元素。 例如: 如下图所示,设m=4,n=5。 当x[1]=1时,2张{1,1}可以贴出邮资2。 这时,设x[2]=3。 将3往{1,1}中添加,产生新的邮资贴法: 5: {3,1,1},8: {3,3,1,1}。 这时,程序需要更新数组y的值。 如果新的贴法比y[5],y[8]已有贴法所用的张数更少,则更新之。 #include usingnamespacestd; classStamp { friendintMaxStamp(int,int,int[]); private: intBound(inti); voidBacktrack(inti,intr); intn;//邮票面值数 intm;//每张信封最多允许贴的邮票数 intmaxvalue;//当前最优值 intmaxint;//大整数 intmaxl;//邮资上界 int*x;//当前解 int*y;//贴出各种邮资所需最少邮票数 int*bestx;//当前最优解 }; voidStamp: : Backtrack(inti,intr) { for(intj=0;j<=x[i-2]*(m-1);j++) if(y[j] for(intk=1;k<=m-y[j];k++) if(y[j]+k y[j+x[i-1]*k]=y[j]+k; while(y[r] r++; if(i>n){ if(r-1>maxvalue){ maxvalue=r-1; for(intj=1;j<=n;j++) bestx[j]=x[j]; } return; } int*z=newint[maxl+1]; for(intk=1;k<=maxl;k++) z[k]=y[k]; for(j=x[i-1]+1;j<=r;j++){ x[i]=j; Backtrack(i+1,r); for(intk=1;k<=maxl;k++) y[k]=z[k]; } delete[]z; } intMaxStamp(intn,intm,intbestx[]){ StampX; intmaxint=32767; intmaxl=1500; X.n=n; X.m=m; X.maxvalue=0; X.maxint=maxint; X.maxl=maxl; X.bestx=bestx; X.x=newint[n+1]; X.y=newint[maxl+1]; for(inti=0;i<=n;i++) X.x[i]=0; for(i=1;i<=maxl;i++) X.y[i]=maxint; X.x[1]=1; X.y[0]=0; X.Backtrack(2,1); cout<<"当前最优解: "; for(i=1;i<=n;i++) cout< cout< delete[]X.x; delete[]X.y; returnX.maxvalue; } voidmain(){ int*bestx; intn; intm; cout<<"请输入邮票面值数: "; cin>>n; cout<<"请输入每张信封最多允许贴的邮票数: "; cin>>m; bestx=newint[n+1]; for(inti=1;i<=n;i++) bestx[i]=0; cout<<"最大邮资: "< } 连续邮资问题问题描述: 假设国家发行了n种不同面值的邮票,并且规定每张信封上最多只允许贴m张邮票。 连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计,在1张信封上可贴出从邮资1开始,增量为1的最大连续邮资区间。 例如,当n=5和m=4时,面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。 问题分析: 如果使用动态规划方法计算数组y的值,状态转移过程: 将x[i-1]加入等价类集S中,将会引起数组x能贴出的邮资范围变大,对S的影响是如果S中的邮票不满m张,那就一直贴x[i-1],直到S中有m张邮票,这个过程会产生很多不同的邮资,取能产生最多不同邮资的用邮票最少的那个元素。 例如: 如下图所示,设m=4,n=5。 当x[1]=1时,2张{1,1}可以贴出邮资2。 这时,设x[2]=3。 将3往{1,1}中添加,产生新的邮资贴法: 5: {3,1,1},8: {3,3,1,1}。 这时,程序需要更新数组y的值。 如果新的贴法比y[5],y[8]已有贴法所用的张数更少,则更新之。 #include usingnamespacestd; classStamp { friendintMaxStamp(int,int,int[]); private: intBound(inti); voidBacktrack(inti,intr); intn;//邮票面值数 intm;//每张信封最多允许贴的邮票数 intmaxvalue;//当前最优值 intmaxint;//大整数 intmaxl;//邮资上界 int*x;//当前解 int*y;//贴出各种邮资所需最少邮票数 int*bestx;//当前最优解 }; voidStamp: : Backtrack(inti,intr) { for(intj=0;j<=x[i-2]*(m-1);j++) if(y[j] for(intk=1;k<=m-y[j];k++) if(y[j]+k y[j+x[i-1]*k]=y[j]+k; while(y[r] r++; if(i>n){ if(r-1>maxvalue){ maxvalue=r-1; for(intj=1;j<=n;j++) bestx[j]=x[j]; } return; } int*z=newint[maxl+1]; for(intk=1;k<=maxl;k++) z[k]=y[k]; for(j=x[i-1]+1;j<=r;j++){ x[i]=j; Backtrack(i+1,r); for(intk=1;k<=maxl;k++) y[k]=z[k]; } delete[]z; } intMaxStamp(intn,intm,intbestx[]){ StampX; intmaxint=32767; intmaxl=1500; X.n=n; X.m=m; X.maxvalue=0; X.maxint=maxint; X.maxl=maxl; X.bestx=bestx; X.x=newint[n+1]; X.y=newint[maxl+1]; for(inti=0;i<=n;i++) X.x[i]=0; for(i=1;i<=maxl;i++) X.y[i]=maxint; X.x[1]=1; X.y[0]=0; X.Backtrack(2,1); cout<<"当前最优解: "; for(i=1;i<=n;i++) cout< cout< delete[]X.x; delete[]X.y; returnX.maxvalue; } voidmain(){ int*bestx; intn; intm; cout<<"请输入邮票面值数: "; cin>>n; cout<<"请输入每张信封最多允许贴的邮票数: "; cin>>m; bestx=newint[n+1]; for(inti=1;i<=n;i++) bestx[i]=0; cout<<"最大邮资: "< } 编辑距离问题 思路: 动态规划 开一个二维数组d[i][j]来记录a0-ai与b0-bj之间的编辑距离,要递推时,需要考虑对其中一个字符串的删除操作、插入操作和替换操作分别花费的开销,从中找出一个最小的开销即为所求 具体算法: 首先给定第一行和第一列,然后,每个值d[i,j]这样计算: d[i][j] = min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+(s1[i] == s2[j]? 0: 1)); 最后一行,最后一列的那个值就是最小编辑距离 四、算法描述及复杂度分析 题目描述: 要求两字符串有差异的字符个数。 例如: aaaaabaaaaa aaaaacaabaa 这两个字符串,最大公共字串长度是5,但它们只有两个字符不同,函数输出值应为2。 如果是: aaabbbcccddd aaaeeeddd 函数的输出值应该是6。 比较形象地形容一下,把两个字符串排成上下两行,每个字符串都可以在任何位置插入空格以便上下对齐,每个列上至少有一个字符来自这两个字符串。 当对齐程度最高
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最小 重量 机器 设计 题目
![提示](https://static.bingdoc.com/images/bang_tan.gif)