Question

C++动态规划

谁能教我一下C++的动态规划 我不是太懂 谁能帮我搞懂了我给50 最好快点在11月半之前 11月27号就是考试了 帮帮忙啊 (详细点 不要发概念或者只发一个程序段)

Answer 1

矩阵相乘动态规划
1.基本思想

在比较基本的算法设计思想里，动态规划是比较难于理解，难于抽象的一种，但是却又十分重要。动态规划的实质是分治思想和解决冗余，因此它与分治法和贪心法类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点。

贪心法的当前选择可能要依赖于已经作出的选择，但不依赖于还未做出的选择和子问题，因此它的特征是由顶向下，一步一步地做出贪心选择，但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解。相比而言，动态规划则可以处理不具有贪心实质的问题。

在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。

比较感性的说，其实动态规划的思想是对贪心算法和分治法的一种折衷，它所解决的问题往往不具有可爱的贪心实质，但是各个子问题又不是完全零散的，这时候我们用一定的空间来换取时间，就可以提高解题的效率。

2.程序

#include "iostream.h"

#include "stdio.h"

#define N 5

void Traceback(int i,int j,int s[][N])

{

if(i==j)return;

Traceback(i,s[i][j],s);

Traceback(s[i][j]+1,j,s);

cout<<"Multiply A"<<i<<","<<s[i][j];

cout<<"and A"<<(s[i][j]+1)<<","<<j<<endl;

}

void MatrixChain(int *p,int n,int m[][N],int s[][N])

{ int i,r,j,k,t;

for(i=1;i<=n;i++)m[i][i]=0;

for(r=2;r<=n;r++)

for(i=1;i<=n-r+1;i++)

{j=i+r-1;<br/><br/>m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];<br/><br/>s[i][j]=i;<br/><br/>for(k=i+1;k<j;k++)<br/><br/>{ t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; <br/><br/>if(t<m[i][j])<br/><br/>{m[i][j]=t;<br/><br/>s[i][j]=k;<br/><br/>}

}

}

}

void main()

{

cout<<"动态规划求矩阵连乘计算次序最优解:\n";

int s[N][N];

int p[N];

int m[N][N];

int i;

cout<<"初始化N=5个矩阵行列数:\n";

for(i=0;i<N;i++)

cin>>p[i];

cout<<"输出结果:\n";

MatrixChain(p,N,m,s);

Traceback(1,N,s);

}

Answer 2

http://dev.21tx.com/2005/05/05/11352.html你上这个看看。对你有帮助吧！