（动态规划）菜鸟求一些问题的动态转移方程详解

Question

下面的题都是刘汝佳算法竞赛入门经典里的，不过题目网上应该找的到。1.数字三角形问题：d（i,j）=a(i,j)+max{d(i+1,j),d(i+1,j+1)
2.0-1背包问题:f(i,j)=max{f(i-1,j),f(i-1,j-v[i])+w[i]}
请就题解释，并请用通俗点的语言解释，我对很多术语都不是很了解，谢谢啦！哦，顺便再说一句，本人只学过C＋＋和VB,对其他语言完全不懂，所以如需运用程序语言，请尽量用C++或C语言解释。本人将不胜感激！

Answer 1

1是这样的:
d[i][j]表示：加到第i层的第j个数时数值之和的最大值。
a[i][j]表示：第i层的第j个数的值。
max（x,y)就是从x,y里挑个较大的数。
举个例子吧：
--------2
------6 2
----1 8 4
--1 5 6 8
看做这样方便一些：
2
6 2
1 8 4
1 5 6 8
里面的“4”就是第3行第3个数。
f[3][3]=a[3][3]+max(f[4][3],f[4][4])=4+maxn(6,8)=4+8=12
依此推到f[1][1].
注意，因为是由f[i+1][j]和f[i+1][j+1]推出f[i][j]，所以要先有f[i+1][j]和f[i+1][j+1],才能有f[i][j].
所以状态转移（就是由一个值推另一个值）是从下到上的。
所以i循环应该是for (i=n;i>=1;i--)
j循环从前往后或从后往前都无所谓。
好了，1题就倒这里。
2.f[i][j]表示：从前i个物品里，挑出总质量不超过j的若干个东西时，最大能得到的总价值。
所以，第i个物品放包里值还是不放包里值呢？
f[i-1][j]表示第i个物品不放包里。
f[i-1][j-v[i]]+w[i]表示第i个物品放包里。虽然价值增加了w[i],不过放进去之前包里物品的体积不能超过j-v[i],否则就放不进去了。
所以，当f[i-1][j]比较大时，f[i][j]=f[i-1][j],因为第i个物品没放进去，所以跟取前i个物品中的若干个和取前i-1个物品中的若干个的意思是一样的。
f[i-1][j-v[i]+w[i]比较大时，f[i][j]=f[i-1][j-v[i]]+w[i],得到了前i个物品不超过j的体积时能得到的最大的总价值。
注意，当j<v[i]时，f[i][j]必须等于f[i-1][j]，因为第i个物品放不进包。
可以练习一道题:noip2005采药。
祝君学c++愉快。

Answer 2

（即要解出这个问题就必须解出它的子问题）。那么就可以根据它与子问题的关系得到一个状态转移方程。 但动态规划的意义在于，如果多个子问题都包含相同的“

Answer 3

这里解释下01背包
基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是：
f[i][v] = Max
{
f[i − 1][v]//不放第i个物品恰好放入v体积所得价值
f[i − 1][v − c[i]] + w[i]//放第i个物品后 还能放v - c[i] 体积 价值+ w[i]}

应该懂了吧
手打 不易