余姚市城乡建设局网站,cms系统搭建,为客户网站做产品描述,wordpress双栏一、基础知识
动态规划的基本思想#xff1a;将待求解问题分解成若干个子问题#xff0c;如果各个子问题不是独立的#xff0c;不同的子问题的个数只是多项式量级#xff0c;为避免大量的重复计算#xff0c;用一个表记录所有已解决的子问题的答案#xff0c;而在需要的…一、基础知识
动态规划的基本思想将待求解问题分解成若干个子问题如果各个子问题不是独立的不同的子问题的个数只是多项式量级为避免大量的重复计算用一个表记录所有已解决的子问题的答案而在需要的时候再找出已求得的答案。 分治与动态规划算法的异同 相似之处:
都可以将大问题划分为小问题求解。都需要重叠子问题的最优解。
不同之处: 分治算法是自上而下,递归求解,然后合并结果。动态规划是自下而上,从更小的子问题开始递推。 分治算法对每个子问题只计算一次,不会重复计算。动态规划算法会存储每个子问题的解,重复使用,避免重复计算。 分治算法不需要存储中间结果,只存储最终结果。动态规划需要创建一个表来存储各个子问题的解。 分治算法对每个子问题的解需要进行合并,而动态规划只需要简单地查表即可得到解。 分治算法的时间复杂度较高,常为O(nlogn)。动态规划能达到O(n)的时间复杂度。 总之,分治算法采用自上而下的分解方式,只存储最终结果,要进行结果合并,效率较低。动态规划采用自下而上递推的方式,存储每个子问题的最优解,通过查表得到最终解,效率较高。
理解动态规划算法的基本要素
最优子结构性质问题的最优解包含了其子问题的最优解。重叠子问题性质有些子问题被反复计算多次。
动态规划算法求解问题的步骤
找出最优解的性质并刻画其结构特征递归地定义最优值以自底向上的方式计算出最优值构造最优解
二、矩阵连乘问题 伪代码
//用动态规划法求解
void MatrixChain(int *pint nint **mint **s)
{for (int i 1; i n; i) m[i][i] 0;//矩阵链长度为1for (int r 2; r n; r) //r为矩阵链长度从2…nfor (int i 1; i n - r1; i) {//遍历所有长度是r的子问题。//对于每一个给定的链长r左边界为i右边界为jint jir-1;m[i][j] ∞; s[i][j] i;//记录断开位置即加括号的位置for (int k i; k j; k){//矩阵链的分隔位置从第i个矩阵…第j-1个矩阵int t m[i][k] m[k1][j] p[i-1]*p[k]*p[j];if (t m[i][j]) { m[i][j] t; s[i][j] k;}}}
}三、最长公共子序列问题 int LCSLength(char *x,char *y,int c[ ][N],int b[ ][N])
{ //x和y的长度 int mstrlen(x),nstrlen(y); int i,j; //初始化c[][] for (i 0; i m; i) c[i][0] 0; for (i 0; i n; i) c[0][i] 0; //计算c[][]for (i 1; i m; i) for (j 1; j n; j){//如果两个字符相同,左上方的值加1 if (x[i-1]y[j-1]) { c[i][j]c[i-1][j-1]1; b[i][j]1; } //如果不相同,取左方和上方的最大值 else if (c[i-1][j] c[i][j-1]) { c[i][j]c[i-1][j]; b[i][j]2; } else { c[i][j]c[i][j-1]; b[i][j]3; } } //返回最长公共子序列长度return c[m][n];
}
//通过b[][]回溯构造最长公共子序列
void LCS(int i,int j,char *x,int **b)
{ //到达边界,返回 if (i 0 || j0) return; //向左上方移动 if (b[i][j] 1){ LCS(i-1,j-1,x,b); coutx[i]; } //向左方移动else if (b[i][j] 2) LCS(i-1,j,x,b); //向上方移动else LCS(i,j-1,x,b);
}四、最大子段和问题 int maxSum(int a[],int n,int begin,int end){int sum0; //结果,最大子序列和int b0; //当前和for(int i0;in;i){if(b0) ba[i]; //如果b大于0,加上当前元素 else{ ba[i]; //如果b等于0,重新开始,b赋值为当前元素值begini; //记录开始位置 }if(bsum){ //如果当前和大于结果,更新结果和结尾位置 sumb; endi; } }return sum; //返回结果
}
五、0-1背包问题 int Knapsack(int v[], int w[], int c, int n, m[][])
{ //初始化第一行和第一列,均为0for(int i0;in;i) m[i][0]0; for(int j0;jc;j) m[0][j]0; //自底向上计算每个子问题的最优值for(i1;in;i) for(j1;jc;j){ //如果不能装下,最大价值就是不考虑该物品的价值if(jw[i]) m[i][j]m[i-1][j]; //如果能装下,取决于装入或不装入该物品的最大值elsem[i][j]max(m[i-1][j], m[i-1][j-w[i]]v[i]);} //返回总的最大价值return m[n][c];
}
