intm = 17;//背包容量
intn = 5;//物品个数
//c[i][j]表示前i个物品能装入容量为Wj的背包中的最大价值
intc[][] =newint[n+1][m+1];
intpath[][] =newint[n+1][m+1];
//初始化第一列和第一行
for(inti=0;i<c.length;i++){
动态规划算法是非常有效的算法技术，那么什么时候使用它呢？或者说其运用场景是什么？若求解问题具有一下性质，可以考虑使用动态规划法：
1、最优子结构：如果一个问题的最优解中包含其子问题的最优解，就是说该问题具有最优子结构。这时候贪婪算法可能也使用求解此类问题
2、重叠子问题：重叠子问题是指用来求解问题的递归算法可以反复的解同样的问题，而不是总在产生新的问题，即当一个递归算法不断的调用同一个问题时，就说该问题包含重叠子问题，此时若使用分治法递归求解时，则每次遇到子问题都会视为新问题，会极大降低效率，而动态规划法对每个子问题仅计算一次，把解保存到在一个需要时就可以查看的表中
根据上述分析，设c[i , w]表示背包容量为w时i个物品最优解的总价值，得到公式：
0i = 0或w = 0
C[i , w ] =c[i – 1, w] wi > w
max{ c[i–1 ,w–wi ] + vi , c[i – 1,w]} i > 0且wi <= w
2、根据物品的件数i = 5、包的容量W = 17规划“价值”分布矩阵，如下图所示：
{
int i,w;
//为二维数组申请空间
int** c = (int**)malloc(sizeof(int *)*(n+1));
for(i=0;i<=n;i++)
c[i] = (int *)malloc(sizeof(int)*(W+1));
//初始化二维数组
for(w=0;w<=W;w++)
c[0][w]=0;
for(i=1;i<=n;i++)
{
c[i][0]=0;
for(w=1;w<=W;w++)
{
//如果背包剩余重量大于物品重量
if(Weights[i-1]<=w)
{
if(Values[i-1]&> c[i-1][w])
{
//重量为w的背包中放入该物品
c[i][w]=Values[i-1]+c[i-1][w-Weights[i-1]];
动态规划算法通常用于求解具有某种最优性质的问题。这类问题中，可能会有许多可行的解，每个解对应个值，我们希望找到最大值或者最小值的那个解，其步骤如下：
1、找出最优值的性质，并分析其结构特征
2、递归定义最优解的值
3、自底向上的方式计算出最优值
4、根据计算最优值得到的信息，构造一个最优解
步骤1—2是基本步骤，在只需求出最优值的情况下步骤4可以省略。若需要求子问题的最优解，则必须执行步骤4，此时在步骤3中计算最优值时，通常记录等多的信息，以便在步骤4中根据所记录的信息快速构造出一个最优解
}else{
c[i][Wj] = c[i-1][Wj];
}
}
}
}
for(inti=0;i<c.length;i++){
for(intj=0;j<c[0].length;j++){
System.out.print(c[i][j]+" ");
}
System.out.println();
}
inti=c.length-1;
intj=c[0].length-1;
while(i>0&&j>0){
if(path[i][j] == 1){
System.out.print("第"+i+"个物品装入");
j -= goods_weight[i-1];
}
i--;
}
}
2、C/C++代码实现如下：
int** demo(int n, int W ,int* Weights,float* Values)
c[i][Wj] = c[i-1][Wj];
else{
if(c[i-1][Wj]<c[i-1][Wj-goods_weight[i-1]]+goods_value[i-1]){
c[i][Wj] = c[i-1][Wj-goods_weight[i-1]]+goods_value[i-1];
path[i][Wj] = 1;
c[i][0] = 0;
}
for(inti=0;i<c[0].length;i++){
c[0][i] = 0;
}
//通过公式迭代计算
for(inti=1;i<c.length;i++){
for(intWj=1;Wj<c[0].length;Wj++){
if(goods_weight[i-1]>Wj)
（1）物品价值重量关系表
（2）物品件数—价值分布矩阵
（二）程序实现
1、Java语言代码实现如下：
publicstaticvoidmain(String[] args) {
int[] goods_weight = {3,4,7,8,9};//物品重量
int[] goods_value = {4,5,10,11,13};//物品价值
动态规划法求解0-1背包问题
一、动态规划法的设计思想
动态规划法是数学--“运筹学”中一个决策分析的实现，广泛运用在计算机算法、企业决策、市场营销等领域
动态规划法是将待求解的问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经过分解的子问题往往不是独立的。若用分治法求解这类问题，则相同的子问题会被求解多次，以至于最后解决问题需要消耗指数级别的时间。然而，不同子问题的数目常常只有多项式量级。如果能够保存已经解决的子问题的答案，在需要时再找出已经求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，可以使用个表来记录已经解决子问题的答案，不管子问题以后是否被用到，只要它计算过，就将其结果填入表中，这就是动态规划法的基本思路
}else{
//重量为w的背包中不放入该物品
c[i][w]=c[i-1][w];
}
}else{
c[i][w] = c[i-1][w];
}
}
}
return c;
}
11
13
重量w
3
4
7
8
9
（一）、求解思路
1、使用矩阵规划出最优解
把求解过程看作是一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包
（1）如果一个问题的最优解包含了物品n，即Xn=1，那么其余的X1,X2,….Xn-1一定构成子问题1,2,……n-1在容量为W-wn时的最优解
（2）如果这个最优解不包含物品n，即Xn=0，那么其余X1,X2….,Xn-1一定构成子问题1,2….,n-1在容量为W时的最优解
二、动态规划法案例：0-1背包问题
有n个物品，第i个物品的价值为Vi，重量为Wi，其中Vi和Wi均为非负数，背包容量为W，W为非负数。现考虑如何选择装入背包的物品，使装入背包的物品总价值最大。假设商品有5件，n=5，容量为17，W=17
要装入的物品及其价值如下表所示：
物品编号
1
2
3
4
5
价值v
4
5
10