动态规划问题求解步骤

动态规划求解步骤：

a. 找出最优解的性质，并刻划其结构特征。

b. 递归地定义最优值。

c. 以自底向上的蔽坦方式计算出最优值。

d. 根据计算最优值时得到的信息，构造最优解

动态规宏灶桐划是由 Dynamic Programming 翻译过来的。动态规划的概念是由美国数学家R.E. Bellman等人提出的，应用于工程领辩悄域。

动态规划是是求解多阶段决策过程(decision process)的最优化问题一种方法。

1.动哪姿态规划#include<stdio.h>

#include<stdlib.h>

#include<time.h>#define N 100 //货物的种类

#define M 10 //货物的质量（千克）typedef struct good

{

int no //第几码缓册个物品

int w //质量

int p //可获利迟宏

int flag

float pw //获得的最高利润

}Goodvoid initGoodSet(Good a[],int n,int m)

int planning(Good a[], int m,int n)//动态规划void initGoodSet(Good a[], int n, int m)

{

int i

srand(time(NULL))

for(i=0i<ni++)

{

a[i].no=i+1

a[i].w=rand()%m+1

a[i].p=rand()%n+1

a[i].pw=(float)a[i].p/a[i].w

}

}int planning(Good a[], int m,int n) //动态规划

{

int c[N+1][M+1]

int i,j

for(i=0i<=Ni++)

for(j=0j<=Mj++)

c[i][j]=0

for(i=1i<=Ni++)

for(j=1j<=Mj++)

if(a[i-1].w<=j)

if(a[i-1].p+c[i-1][j-a[i-1].w]>c[i-1][j])

c[i][j]=a[i-1].p+c[i-1][j-a[i-1].w]

else

c[i][j]=c[i-1][j]

else

c[i][j]=c[i-1][j]

for(i=N,j=Mi>=1i--)//倒推求最优解

if(c[i][j]>c[i-1][j])

{

a[i-1].flag=1

j=j-a[i-1].w

}

return (c[n][m])

}void main()

{

double Start,End

Good a[N]

Start=clock()

initGoodSet(a,N,M)

printf("共获利%d\n",planning(a,M,N))

End=clock()

printf("所需时间为:%lf\n",(End-Start)/1000)

}

---