《计算机算法设计与分析实验.doc》由会员分享，可在线阅读，更多相关《计算机算法设计与分析实验.doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 实验2代码截图和运行结果截图 网工二班 陈衍席 矩阵连乘代码:#include stdafx.h #include using namespace std; const int L = 7; int LookupChain(int i,int j,int *m,int *s,int *p); int MemoizedMatrixChain(int n,int *m,int *s,int *p); void Traceback(int i,int j,int *s);/构造最优解 int main() int pL=30,35,15,5,10,20,25; int *s = new int *
2、L; int *m = new int *L; for(int i=0;iL;i+) si = new intL; mi = new intL; cout矩阵的最少计算次数为：MemoizedMatrixChain(6,m,s,p)endl; cout矩阵最优计算次序为：endl; Traceback(1,6,s); return 0; int MemoizedMatrixChain(int n,int *m,int *s,int *p) for(int i=1; i=n; i+) for(int j=1; j0) return mij; if(i=j) return 0; int u = L
3、ookupChain(i,i,m,s,p) + LookupChain(i+1,j,m,s,p)+pi-1*pi*pj; sij=i; for(int k=i+1; kj; k+) int t = LookupChain(i,k,m,s,p) + LookupChain(k+1,j,m,s,p) + pi-1*pk*pj; if(tu) u=t; sij = k; mij = u; return u; void Traceback(int i,int j,int *s) if(i=j) return; Traceback(i,sij,s); Traceback(sij+1,j,s); cout
4、Multiply Ai,sij; cout and A(sij+1),jendl; 程序运行图： 0-1背包问题代码：#includeint V200200;/前i个物品装入容量为j的背包中获得的最大价值int max(int a,int b) if(a=b) return a; else return b; int KnapSack(int n,int w,int v,int x,int C) int i,j; for(i=0;i=n;i+) Vi0=0; for(j=0;j=C;j+) V0j=0; for(i=0;i=n-1;i+) for(j=0;j=C;j+) if(j=0;i-)
5、if(VijVi-1j) xi=1; j=j-wi; else xi=0; printf(选中的物品是:n); for(i=0;in;i+) printf(%d ,xi); printf(n); return Vn-1C; void main() int s;/获得的最大价值 int w15;/物品的重量 int v15;/物品的价值 int x15;/物品的选取状态 int n,i; int C;/背包最大容量 n=5; printf(请输入背包的最大容量:n); scanf(%d,&C); printf(输入物品数:n); scanf(%d,&n); printf(请分别输入物品的重量:n); for(i=0;in;i+) scanf(%d,&wi); printf(请分别输入物品的价值:n); for(i=0;in;i+) scanf(%d,&vi); s=KnapSack(n,w,v,x,C); printf(最大物品价值为:n); printf(%dn,s); 程序运行图：