动态规划基本思想：
动态规划法通常用于求解具有某种最优性质的问题。当一个问题的解可以看成是一系列子问题的解时，可以利用动态规划方法设计其求解方法。在这类问题中，可能会有许多可行解，希望从中找出具有最优值的解。动态规划与分治法有些类似，其基本思想也是将待求解问题分解为若干子问题，先求子问题，然后从子问题的解得到原问题的解。动态规划与分治法不同的是：适用于动态规划求解的问题，分解得到的子问题往往不是互相独立的。若用分治法来解决这类问题 ，因各子问题的解是相互依赖的，子问题会被重复计算多次。如果能够保存已解决的子问题的答案，而在需要时利用这些已求的答案，就可以避免大量重复计算，节省时间。一般用一个表记录所有的已解决的子问题的答案。不管子问题以后是否被用到，只要它被计算过，就将其结果计入表中。
举一个经典的动态规划实例来加深理解：有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
问题补充：
一件物品i不可能装入背包多次。在选择物品的时候，对每一件物品i只有两种选择：即装入背包或不装入背包。因此，该问题被称为0-1背包问题。
问题分析：
动态规划法的两个核心问题：①将问题划分为子问题；②找出子问题的依赖关系，即求解子问题的递推公式。
令V(i,j)表示在前i(1<=i<=5)个物品中能够装入承重为j(1<=j<=10)的背包中的物品的最大价值，即子问题为求V(i,j)，则可以得到如下递推公式: (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) j<wi （wi为第i个物品的重量） (3) V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) } （j>wi） 上面的(2)式表明：如果第i个物品的重量大于背包的容量，即物品i不能装入背包，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的；(3)式表明:如果第i个物品的重量小于背包的容量，则会有两种情况：①如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi 的背包中的价值加上第i个物品的价值vi; ②如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的最大价值。显然，二者较大值为把前i个物品装入容量为j的背包中的最优解。
明白上述思想后，写代码就比较简单，下面为博主的C++代码：
#include<iostream> using namespace std; const int goodsnum=5;//物品数量 const int bagweight=10;//背包最大承重 int value[5]={6,3,5,4,6};//物品价格 int weight[5]={2,2,6,5,4};//物品重量 int BagMaxValue(int value[],int weight[],int goodsnum,int bagweight);//返回背包最大总价值 int BagMaxValue(int value[],int weight[],int goodsnum,int bagweight) { //创建二维子问题矩阵并初始化（记录子问题的答案） int **matrix=new int*[goodsnum+1];//创建的二维数组大小为matrix[6][11]，以适用上述递推公式 for(int i=0;i<goodsnum+1;i++) matrix[i]=new int[bagweight+1]();//初始化为零 //动态规划递推公式 for(int i=1;i<=goodsnum;i++) for(int j=1;j<=bagweight;j++) { if(j<weight[i-1])//第i个物品的重量为weight[i-1])，价值为value[i-1] matrix[i][j]=matrix[i-1][j]; else matrix[i][j]=max(matrix[i-1][j],(matrix[i-1][j-weight[i-1]]+value[i-1]));//调用系统函数max } //释放内存 int maxvalue=matrix[goodsnum][bagweight]; for(int i=0;i<goodsnum+1;i++) delete [] matrix[i]; delete []matrix; //返回背包最大总价值 return maxvalue;