一、主要概念
使用动态规划求解问题，最重要的是确定动态规划三要素：
（1）问题的阶段
（2）每个阶段的状态
（3）从前一个阶段转化到下一个阶段之间的递推关系
确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题的状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径、最长公共子序列、最大价值等）
二、动态规划在（0-1）背包问题中的应用
1、那么对应动态规划求解的三要素，考虑（0-1）背包问题：
（1）问题的阶段是由物品序列确定的（依次为：仅考虑前一个物品（可以认为是第一个阶段）；仅考虑前两个物品（可以认为是第二个阶段）；仅考虑前三个物品（可以认为是 第三个阶段）.......）
（2）每个阶段的状态，这个状态是由背包容量序列来确定的。（也可以认为i,j确定一个唯一状态）
（3）这个是动态规划的核心，也即状态转移。这一步主要是在判断要不要把第i个物品，放入到状态（容量）为j的背包里面。判断的条件为，包含物品i（f（n-1,m-w[n]）+V（n,m））和不包含物品i（f（n-1,m））的价值比较。
2、解释式子f（i-1,j-w[i]）+V[i]
如果将物品i放入到背包里面，需要在总共的空间j里面腾出w[i]的空间，然后加上物品i的价值。其实这个式子用到了动态规划的两个性质：
（1）最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
（2）无后效性：即某阶段某一状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
3、实际编程
题目描述：
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
<span style="font-size:12px;">#include<iostream>
#include<windows.h>
using namespace std;
#define N 5
#define M 10
#define max(x,y) (x)>(y)?(x);(y)
int main()
{
int f[N+1][M+1];
int w[N];
int v[N];
int result[N+1];
w[0] = 2;
w[1] = 2;
w[2] = 6;
w[3] = 5;
w[4] = 4;
v[0] = 6;
v[1] = 3;
v[2] = 5;
v[3] = 4;
v[4] = 6;
for (int j = 0; j <=M; j++)
{
f[0][j] = 0;
}
for (int i = 1; i <= N; i++)
{
for (int j = 0; j <= M; j++)
{
if (j < w[i-1])
{
f[i][j] = f[i - 1][j];
}
else
{
if (f[i - 1][j]>=f[i - 1][j - w[i-1]] + v[i-1])
{
f[i][j] = f[i - 1][j];
result[i] = 0;
}
else
{
f[i][j] = f[i - 1][j - w[i-1]] + v[i-1];
result[i] = 1;
}
}
}
}
cout << f[N][M]<<endl;
for (int i = 1; i <= N; i++)
{
cout << result[i] << endl;
}
system("pause");
return 0;
}</span>