宁波网站建设制作报价,建设的网站打开速度很慢,常州app网站,旅游电子商务的三创赛网站建设一、实验目的
1#xff0e;加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握#xff1b; 2#xff0e;提高学生利用课堂所学知识解决实际问题的能力#xff1b; 3#xff0e;提高学生综合应用所学知识解决实际问题的能力。
二、实验任务
用动态…一、实验目的
1加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握 2提高学生利用课堂所学知识解决实际问题的能力 3提高学生综合应用所学知识解决实际问题的能力。
二、实验任务
用动态规划算法实现
1、矩阵链相乘问题 2、投资问题 3、求解完全背包问题
问题描述有n种重量和价值分别为wi、vi1≤i≤n的物品从这些物品中挑选总重量不超过W的物品求出挑选物品价值总和最大的挑选方案这里每种物品可以挑选任意多件。4、数字三角形 问题描述在上面的数字三角形中寻找一条从顶部到底边的路径使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。
4、数字三角形
问题描述在上面的数字三角形中寻找一条从顶部到底边的路径使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。 用贪心算法实现
5、最小生成树问题Prim算法和Kruskal算法
设G(VE)是一个无向连通网生成树上各边的权值之和称为该生成树的代价在G的所有生成树中代价最小的生成树称为最小生成树Minimal Spanning Trees。
6、背包问题 【问题描述】设有编号为1、2、…、n的n个物品它们的重量分别为w1、w2、…、wn价值分别为v1、v2、…、vn其中wi、vi1≤i≤n均为正数。 有一个背包可以携带的最大重量不超过W。求解目标在不超过背包负重的前提下使背包装入的总价值最大即效益最大化与0/1背包问题的区别是这里的每个物品可以取一部分装入背包。
三、实验设备及编程开发工具
实验设备惠普Win10电脑 开发工具Java和python环境下eclipse和pycharm编程工具
四、实验过程设计算法思路及描述代码设计
一矩阵相乘问题
基本原理和思路 1、动态规划的第一步寻找最优子结构。为方便起见使用Ai…j表示AiAi1…Aj的乘积结果矩阵。对于k(ikj), 计算Ai…j所需要的计算量为Ai…k 和 Ak1…j 以及二者相乘的代价和。 2、设m[i][j]为Ai…j的最优计算顺序所要花费的代价。则其求解公式为 if i j, m[i][j] 0; //因为只有一个矩阵时计算代码为0即不需要计算。 m[i][j]min{m[i][k] m[k1][j] Pi-1PkPj} ikj 3、为了能够输出求解顺序需要保存区间中的一些分割点。假如Ai…j中的最优分割点为k则我们使用s[i][j]k。即在Ai…j中分别计算Ai…k 和 Ak1…j 所用的计算开销最小。 4、采用自底向上的表格法。依次求解矩阵长度为2,3,…,n的最优计算顺序。
代码实现如下
#include stdio.h
int m[1002][1002],s[1002][1002];
void matrix_chain(int a[], int n)
{int l, i, j, k, tmp;for(l2; ln; l){for(i1; in-l1; i) //长度为l的区间其最小下标为1n-l1{jil-1;m[i][j] 0x7fffffff;for(ki; kj; k) //i~k, k1~j, 所以kj{tmp m[i][k]m[k1][j]a[i-1]*a[k]*a[j];if(tmp m[i][j]){m[i][j] tmp;s[i][j] k;}}}}}
void print(int i, int j)
{if(i j)printf(A%d,i);else{printf(();print(i, s[i][j]);print(s[i][j]1, j);printf());}
}
int main()
{int n, a[1002];int i,j,l;while(scanf(%d,n)1) //输入有n个矩阵{for(i0; in1; i)scanf(%d,a[i]);//memset(m, 0x7fffffff,sizeof(m));for(i0; in1; i)m[i][i] 0;matrix_chain(a, n);printf(%d\n,m[1][n]);print(1, n);printf(\n);}return 0;
} 分析时间复杂度为O(N3) 我们只需要存储一个矩阵就可以了所以空间复杂度是 O(N2)。
二投资问题
基本原理和思路假设分配给第 i 个项目的钱数是 xi问题描述为 目标函数max{f1(x1)f2(x2)…fn(xn)} 约束条件x1x2…xnm,xi∈N设Fk(x)表示x元投给前k个项目的最大效益k1,2,…,nx1,2,…,m递推方程Fk(x)max{fk(xk)Fk-1(x-xk)}(0≤xk≤x)k2,3,…,n边界条件F1(x)f1(x),Fk(0)0,k1,2,…,n*说明第k步前后共分配x万元分配给第k个项目xkx-xk万元分配给前k-1个项目
代码实现如下
#include iostream
#include vectorusing namespace std;int main() {int m, n;//m元钱n项投资int i, j;int tmp_m, tmp_F 0;cout 请输入投资金额和项目数 endl;cin m n;vectorvectorint f(n, vectorint(m 1));//f[i][x], 0in,0xmvectorvectorint F(n, vectorint(m 1));//F[i][x]将x元钱投入到前i个项目上最大的收益//在第(i1)个项目上投入0元收益为0注意i从0开始for (i 0; i n; i) {f[i][0] 0;}cout 请输入各项目对应投资金额的收益从1开始 endl;for (i 0; i n; i) {for (j 1; j m 1; j) {cin f[i][j];}}//初始化给F[0][0-m]赋值for (j 0; j m 1; j) {F[0][j] f[0][j];//第一个项目上投入0-m元钱的最大收益等于f[0][0-m]}for (i 1; i n; i) {//项目编号从1开始for (j 0; j m 1; j) {//钱数,从0开始for (tmp_m 0; tmp_m j; tmp_m) {//递推公式tmp_F F[i - 1][j - tmp_m] f[i][tmp_m];//取最大值if (tmp_F F[i][j]) {F[i][j] tmp_F;} }}}cout 最大总收益: F[n - 1][m] endl;
}
分析复杂度 W(n,m)O(nm2)。
三 求解完全背包问题
基本原理和思路1.设置动态规划二维数组dpdp[i][j]表示从前i个物品中选出重量不超过j或者剩余容量为j)的物品的最大总价值。 ①显然有边界条件dp[i][0]0(背包不能装入任何物品时总价值为0dp[0][j]0没有任何物品可装入时总价值为0可以采用memset函数一次性初始化为0. ②另外设置二维数组fk其中fk[i][j]存放dp[i][j]得到最大值时物品i挑选的件数。
代码实现如下
//求解完全背包问题的算法
#include stdio.h
#include string.h
#define MAXN 20 //最多物品数
#define MAXW 100 //最大限制重量
#define max(x,y) ((x)(y)?(x):(y))
//问题表示
int n,W;
int w[MAXN],v[MAXN];
//求解结果表示
int dp[MAXN1][MAXW1],fk[MAXN1][MAXW1];
int solve() //求解多重背包问题
{int i,j,k;for (i1;in;i){for (j0;jW;j)for (k0;k*w[i]j;k){if (dp[i][j]dp[i-1][j-k*w[i]]k*v[i]){dp[i][j]dp[i-1][j-k*w[i]]k*v[i];fk[i][j]k; //物品i取k件} }}return dp[n][W];
}
void Traceback() //回推求最优解
{int in,jW;while (i1){printf(物品%d共%d件 ,i,fk[i][j]);j-fk[i][j]*w[i]; //剩余重量i--;}printf(\n);
}
void prin(){ //查看dp数组与fk数组 int i,j,k;printf(fk[i][j]:\n);for (i1;in;i){for (j0;jW;j){printf(%d ,fk[i][j]);}printf(\n);}printf(dp[i][j]:\n);for (i1;in;i){for (j0;jW;j){printf(%d ,dp[i][j]);}printf(\n);}
}
int main()
{w[1]3; w[2]2; w[3]6;w[4]2;v[1]7; v[2]2; v[3]5;v[4]3;n4; W9;memset(dp,0,sizeof(dp));memset(fk,0,sizeof(fk));printf(最优解:\n);printf( 总价值%d\n,solve());printf( 方案: );Traceback();printf(\n);prin();return 0;
} 分析空间复杂度O(nV) 时间复杂度O(nV)。
四数字三角形
基本原理和思路MaxSum(i,j)从第i行j列到底边的最大数字之和 从最后一行开始递推MaxSum(n,j)D(n,j)//n行j列MaxSum(n-1,j) D(n-1,j) max( MaxSum(n,j) , MaxSum(n,j1) ) 然后为了减少空间不需要用二维数组来存储MaxSum(n,j)的值只需要求MaxSum(n,j)的时候存储下一行MaxSum(n1,j)的值就可以然后计算完第n行的MaxSum之后再覆盖原来的第n1行的MaxSum的值。
代码实现如下
#include iostream
#include algorithm
using namespace std;
#define Max 101
int D[Max][Max];
int n;
int maxSum[Max][Max];
int MaxSum(int i,int j)
{if(maxSum[i][j]!-1)return maxSum[i][j];if(in)maxSum[i][j]D[i][j];else{int xMaxSum(i1,j);int yMaxSum(i1,j1);maxSum[i][j]max(x,y)D[i][j];}return maxSum[i][j];
}
int main()
{int i,j;cinn;for(i1;in;i)for(j1;ji;j){cinD[i][j];maxSum[i][j]-1;}coutMaxSum(1,1)endl;return 0;
}
分析时间复杂度是n2。
五最小生成树问题
prim算法
基本原理和思路设G(V, E)是具有n个顶点的连通网 T(U, TE)是G的最小生成树 T的初始状态为U{u0}u0∈VTE{ } 重复执行下述操作 在所有u∈Uv∈V-U的边中找一条代价最小的边(u, v)并入集合TE同时v并入U直至UV。 数组lowcost[n]用来保存集合V-U中各顶点与集合U中顶点最短边的权值lowcost[v]0表示顶点v已加入最小生成树中 数组adjvex[n]用来保存该边所依附的集合V-U中各顶点与集合U中顶点的最短边集合U中的顶点。
代码实现如下
void prime(MGraph G){for(int i1;iG.vertexNu;i){lowcost[i]G.arc[0][i]; adjvex[i]0;}lowcost[0]0;for(i1;iG.vertexNum;i){kMinEdge(lowcost,G.vertexNum)coutKadjvex[k]lowcost[k];lowcost[k]0;for(j1;jG.vertexNum;j)if((G.arc[k][j]lowcost[j]){lowcost[j]G.arc[k][j];arcvex[j]k;}
}
六背包问题
基本原理和思路利用动态规划思想 子问题为f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。其状态转移方程是f[i][v]max{f[i-1][v],f[i-1][v-c[i]]w[i]} //这个方程非常重要基本上所有跟背包相关的问题的方程都是由它衍生出来的。将前i件物品放入容量为v的背包中”这个子问题若只考虑第i件物品的策略放或不放那么就可以转化为一个只和前i-1件物品相关的问题。 1.如果不放第i件物品那么问题就转化为“前i-1件物品放入容量为v的背包中”价值为f[i-1; v] 2.如果放第i件物品那么问题就转化为“前i-1件物品放入剩下的容量为 v-Ci的背包中”此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值Wi 。
代码实现如下
int n 5;
double W 100;
struct NodeType
{double w;double v;double p;bool operator(const NodeType s)const{return p s.p;}
};NodeType A[] { {0},{10,20},{20,30},{30,66},{40,40},{50,60} };
double V;
double x[MAXN];void Knap()
{V 0;double weight W;memset(x, 0, sizeof(x));int i 1;while (A[i].w weight)//物品可以全部装入{x[i] 1;weight - A[i].w;V A[i].v;i;}if (weight 0)//余下物品重量大于0{x[i] weight / A[i].w;V x[i] * A[i].v;}
}
分析时间复杂度为O(nlog2n)
实验小结包括问题和解决方法、心得体会等
经过这次试验收获颇多代码实现过程中也遇到一些问题有的问题确实也有一定的难度所以也是通过了网络搜索才得出的解决方案思维上得到了很好的训练同时也明白了一个道理纸上得来终觉浅绝知此事要躬行。尤其是算法和编程这门课程更是要勤于动手方能获得收获。希望下次实验或者之后的编程学习能吸取这些教训。
