最小重量机器设计问题

1、最小重量机器设计问题（1）部件有n个，供应商有m个，分别用cij和wij存储从供应商j 处购得的部件i的价格和相应重量，d为总价格的上限，savexi存储第i个部件的的供应商。  （2）用递归函数backtrack(i)来实现回溯法搜索排列树（形式参数i表示递归深度）。     若cp>d，则为不可行解，剪去相应子树，返回到i-1层继续执行。     若cw>=weight，则不是最优解，剪去相应子树，返回到i-1层继续执行。  &#

2、160;  若i>n，则算法搜索到一个叶结点，用weight对最优解进行记录，返回到i-1层继续执行；   用for循环对部件i从m个不同的供应商购得的情况进行选择(1jm）。  （3）主函数调用一次backtrack(1)即可完成整个回溯搜索过程，最终得到的weight即为所求最小总重量，p为该机器最小重量的价格。 代码及结果#include "stdafx.h"#include<iostream>using namespace std;#define N 50class M

3、inWmechineint n; /部件个数int m; /供应商个数int COST; /题目中的Cint cw; /当前的重量int cc; /当前花费int bestw; /当前最小重量int bestxN;int savexN;int wNN;int cNN;public:MinWmechine();void machine_plan(int i);void prinout();MinWmechine:MinWmechine()cw=0; /当前的重量cc=0; /当前花费bestw=-1; /当前最小重量bestxN;savexN;cout<<"请输入部件个数：

4、"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>>wij;cout<<"请

5、输入第 "<<j+1<<" 个供应商的第 "<<i+1<<" 个部件的价格："cin>>cij;if(wij<0 | cij<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+) /把当前搜过的路径记下来savexj=bestxj

6、;return;for(int j=0; j<m; j+) /依次递归尝试每个供应商if(cc+cij<COST)cc+=cij;cw+=wij;bestxi=j;machine_plan(i+1);bestxi=-1;cc-=cij;cw-=wij;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<<" 部件

7、重量："<<wij<<"价格："<<cij<<"n"for(j=0; j<n; j+)bestxj=-1;machine_plan(0);cout<<"n最小重量机器的重量是: "<<bestw<<endl;for(int k=0; k<n; k+)cout<<" 第"<<k+1<<"部件来自供应商"<<savexk+1<<&quo

8、t;n"ccc+=cksavexk;cout<<"n该机器的总价钱是: "<<ccc<<endl;cout<<endl;int main(void)MinWmechine Y;Y.prinout();return 0;矩阵连乘问题【问题】：矩阵链乘问题：给定n个矩阵A1,A2,.,An，其中Ai与Ai+1是可乘的，i=1，2.，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。【解题】：这里我采用的是动态划分算法：设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。

9、(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解(由子结构的最优解得到原先大问题的最优解)。【解题关键】：将一系列相乘的矩阵（Ai.Aj）划分为两部分;即（AiAi+1.Ak）(Ak+1Ak+2.Aj)，k的位置要保证左边括号和右边括号相乘的消耗最小。【思路】：这里我采用两种方法来实现：（1）用三重for循环来实现：根据主对角线的方向及其右边与之平行的对角线方向，由上至下，从左到右分别求出Cij的值，后面要求的值都可以根据前面所求的的值来求。Cij代表矩阵链Ai.Aj相乘的最小消耗。其中：cii=0，i=1,2,.n求解的顺序如下：C12

10、,C23,C23,.,CN-1N,C13,C24.CN-2N.CNN最后得到的CNN的值就是我们所求的。（2）备忘录方法（即递归算法）：将整个矩阵链分成两部分，然后在分别对两边的子矩阵链递归调用算法。【程序代码】：两种方法都在其中：#include<iostream.h>#include<stdlib.h>#include<limits.h>#include<time.h>#define MAX_VALUE 100#define N 201 /连乘矩阵的个数(n-1)#define random() rand()%MAX_VALUE &

11、#160; /控制矩阵的行和列的大小int cNN, sNN, pN;int matrixchain(int n)    /3个for循环实现    for(int k=1;k<=n;k+)        ckk=0;    for(int d=1;d<n;d+)        for(int i=1;i<=n-d;i+)     

12、;       int j=i+d;            cij=INT_MAX;            for(int m=i;m<j;m+)                int t=cim+cm+1j+pi-1*pm*pj; 

13、               if(t<cij)                                    cij=t;       

14、60;           sij=m;                                        return c1n;void Print(int sN,int i,int j) / 

15、输出矩阵连乘积的计算次序    if(i=j)        cout<<"A"<<i;    else            cout<<"("        Print(s,i,sij);  / 左半部子矩阵连

16、乘        Print(s,sij+1,j);  /左半部子矩阵连乘        cout<<")"    int lookupchain(int i,int j)  /备忘录方法    if(cij>0)        return cij;  

17、60; if(i=j)        return 0;    int u=lookupchain(i,i)+lookupchain(i+1,j)+pi-1*pi*pj;    sij=i;    for(int k=i+1;k<j;k+)            int t=lookupchain(i,k)+lookupchain(k+1,j)+pi-

18、1*pk*pj;        if(t<u)                    u=t;            sij=k;                cij=u;

19、    return u;void main()    srand(int)time(NULL);    for(int i=0;i<N;i+)  /  随机生成数组p，各个元素的值的范围：1MAX_VALUE        pi=random()+1;    clock_t start,end;       double elap

20、sed;    start=clock();    /cout<<"Count: "<<matrixchain(N-1)<<endl;   /3重for循环实现    cout<<"Count: "<<lookupchain(1,N-1)<<endl;   /备忘录方法    end=clock();  &

21、#160; elapsed=(double)(end-start);/CLOCKS_PER_SEC;     cout<<"Time: "<<elapsed<<endl;    Print(s,1,N-1);  /输出矩阵连乘积的计算次序    cout<<endl;【总结】：两种算法的时间复杂度均为o(n3)，,随着数据量的增多，备忘录方法消耗的时间越长；我觉得是由于递归算法，随着数据量增大，调用函数的次数也增大，语

22、句被执行的时间也越多，因此调用函数消耗的时间也增多。最优服务次序问题平均等待时间是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<iostream>#include<cstdio>#include<algorithm>#include<vector>#inc

23、lude<iomanip>using namespace std;int x10000;int main() int n;cout<<"请输入顾客的人数n:" cin >> n; int temp; for(int j = 0; j< n; j+) printf("请输入第%d个顾客的服务时间：",j+1); scanf("%d",&xj); sort(x,x+n); for(int i = 1; i < n; i+) xi+=xi-1; double t = 0; for( i

24、 = 0; i < n; i+) t+=xi; t/=n; cout.setf(ios:fixed); printf("最小平均等待时间:"); cout << setprecision(2) << t << endl; system("pause"); return 0;连续邮资问题问题描述:假设国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封 上可贴出从邮资1开始，增量为1的最大连续邮资区间。例如，当n=5和m=4时

25、，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮 资区间是1到70。问题分析:如果使用动态规划方法计算数组y的值，状态转移过程：将xi-1加入等价类集S中，将会引起数组x能贴出的邮资范围变大，对S的影响是如果S中的邮票不满m张，那就一直贴xi-1,直到S中有m张邮票，这个过程会产生很多不同的邮资，取能产生最多不同邮资的用邮票最少的那个元素。 例如：如下图所示，设m=4,n=5。当x1=1时，2张1,1可以贴出邮资2。这时，设x2=3。将3往1,1中添加，产生新的邮资贴法：5:3,1,1，8:3,3,1,1。这时，程序需要更新数组y的值。如果新的贴法比y5，y8已

26、有贴法所用的张数更少，则更新之。#include<iostream>using namespace std;class Stampfriend int MaxStamp(int ,int ,int );private: int Bound(int i); void Backtrack(int i,int r); int n;/邮票面值数 int m;/每张信封最多允许贴的邮票数 int maxvalue;/当前最优值 int maxint;/大整数 int maxl;/邮资上界 int *x;/当前解 int *y;/贴出各种邮资所需最少邮票数 int *bestx;/当前最优解;

27、void Stamp:Backtrack(int i,int r)for(int j=0;j<=xi-2*(m-1);j+)if(yj<m)for(int k=1;k<=m-yj;k+)if(yj+k<yj+xi-1*k)yj+xi-1*k=yj+k;while(yr<maxint)r+;if(i>n)if(r-1>maxvalue)maxvalue=r-1;for(int j=1;j<=n;j+)bestxj=xj;return;int *z=new intmaxl+1;for(int k=1;k<=maxl;k+)zk=yk;for(j

28、=xi-1+1;j<=r;j+)xi=j;Backtrack(i+1,r);for(int k=1;k<=maxl;k+)yk=zk;delete z;int MaxStamp(int n,int m,int bestx)Stamp X;int maxint=32767;int maxl=1500;X.n=n;X.m=m;X.maxvalue=0;X.maxint=maxint;X.maxl=maxl;X.bestx=bestx;X.x=new int n+1;X.y=new int maxl+1;for(int i=0;i<=n;i+)X.xi=0;for(i=1;i<

29、;=maxl;i+)X.yi=maxint;X.x1=1;X.y0=0;X.Backtrack(2,1);cout<<"当前最优解:"for(i=1;i<=n;i+)cout<<bestxi<<" "cout<<endl;delete X.x;delete X.y;return X.maxvalue;void main()int *bestx;int n;int m;cout<<"请输入邮票面值数:"cin>>n;cout<<"请输入每

30、张信封最多允许贴的邮票数:"cin>>m;bestx=new intn+1;for(int i=1;i<=n;i+)bestxi=0;cout<<"最大邮资:"<<MaxStamp(n,m,bestx)<<endl;连续邮资问题问题描述:假设国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封 上可贴出从邮资1开始，增量为1的最大连续邮资区间。例如，当n=5和m=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮

31、资的最大连续邮 资区间是1到70。问题分析:如果使用动态规划方法计算数组y的值，状态转移过程：将xi-1加入等价类集S中，将会引起数组x能贴出的邮资范围变大，对S的影响是如果S中的邮票不满m张，那就一直贴xi-1,直到S中有m张邮票，这个过程会产生很多不同的邮资，取能产生最多不同邮资的用邮票最少的那个元素。 例如：如下图所示，设m=4,n=5。当x1=1时，2张1,1可以贴出邮资2。这时，设x2=3。将3往1,1中添加，产生新的邮资贴法：5:3,1,1，8:3,3,1,1。这时，程序需要更新数组y的值。如果新的贴法比y5，y8已有贴法所用的张数更少，则更新之。#include<

32、iostream>using namespace std;class Stampfriend int MaxStamp(int ,int ,int );private: int Bound(int i); void Backtrack(int i,int r); int n;/邮票面值数 int m;/每张信封最多允许贴的邮票数 int maxvalue;/当前最优值 int maxint;/大整数 int maxl;/邮资上界 int *x;/当前解 int *y;/贴出各种邮资所需最少邮票数 int *bestx;/当前最优解;void Stamp:Backtrack(int i,i

33、nt r)for(int j=0;j<=xi-2*(m-1);j+)if(yj<m)for(int k=1;k<=m-yj;k+)if(yj+k<yj+xi-1*k)yj+xi-1*k=yj+k;while(yr<maxint)r+;if(i>n)if(r-1>maxvalue)maxvalue=r-1;for(int j=1;j<=n;j+)bestxj=xj;return;int *z=new intmaxl+1;for(int k=1;k<=maxl;k+)zk=yk;for(j=xi-1+1;j<=r;j+)xi=j;Back

34、track(i+1,r);for(int k=1;k<=maxl;k+)yk=zk;delete z;int MaxStamp(int n,int m,int bestx)Stamp X;int maxint=32767;int maxl=1500;X.n=n;X.m=m;X.maxvalue=0;X.maxint=maxint;X.maxl=maxl;X.bestx=bestx;X.x=new int n+1;X.y=new int maxl+1;for(int i=0;i<=n;i+)X.xi=0;for(i=1;i<=maxl;i+)X.yi=maxint;X.x1=1

35、;X.y0=0;X.Backtrack(2,1);cout<<"当前最优解:"for(i=1;i<=n;i+)cout<<bestxi<<" "cout<<endl;delete X.x;delete X.y;return X.maxvalue;void main()int *bestx;int n;int m;cout<<"请输入邮票面值数:"cin>>n;cout<<"请输入每张信封最多允许贴的邮票数:"cin>&g

36、t;m;bestx=new intn+1;for(int i=1;i<=n;i+)bestxi=0;cout<<"最大邮资:"<<MaxStamp(n,m,bestx)<<endl;编辑距离问题思路：动态规划开一个二维数组dij来记录a0-ai与b0-bj之间的编辑距离，要递推时，需要考虑对其中一个字符串的删除操作、插入操作和替换操作分别花费的开销，从中找出一个最小的开销即为所求具体算法：首先给定第一行和第一列，然后，每个值di,j这样计算：dij   =   min(di-1j+1,dij-1+1,di-1j-1+(s1i  =  s2j?0:1);   最后一行，最后一列的那个值就是最小编辑距离四、算法描述及复杂度分析题目描述：要求两字符串有差异的字符个数。例如： aaaaabaaaaa aaaaacaabaa 这两个字符串，最大公共字串长度是5，但它们只有两个字符不同，函数输出值应为2。 如果是： aaabbbcccddd aaaeeeddd 函数的输出值应该是6。 比较形象地形容一下，把两个字符串排成上下两行，每个字符串都可以在任何位置插