本文主要是介绍简谈--动态规划1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
动态规划(dynamic programming)
动态规划的适用条件：
１．最优化原理（最优子结构性质）
最优化原理可以这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
２．无后向性
将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
状态和状态转移：
两种情况下背包价值最大者应该是对Xi决策后的背包价值.
令v(i,j)表示在前i(1<=i<=n)个物品中能装入容量为j(1<=j<=C)的背包的物品的最大值,可以得到如下动态规划函数:
V(i,0)=V(0,j)=0;
V(i,j)= V(i-1,j) j<wi
V(i,j)= max{V(i-1,j),V(i-1,j-wi)+vi} j>wi
上面就是0-1背包问题的状态转移方程,这也是动态规划中最难,最重要的,只有找到好的状态和它的转移方程才能用动态规划解决好问题.ans=0;
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
if(i==n)
if(dp[i][j]>ans)
{
ans=dp[i][j];
}
}
}
int k=0;
for(i=1;i<=n;i++) {
for(j=1;j<=weight;j++)
if(j<w[k])
V[k][j]=V[1-k][j];
else
V[k][j]=V[1-k][j]>(V[1-k][j-w[i]]+p[i])?V[1-k][j]:(V[1-k][j-w[i]]+p[i]);
k=1;
}
这篇关于简谈--动态规划1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
