一、动态规划算法介绍
动态规划算法(Dynamic Programming Algorithm, DPA)与分治法类似，其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费过多的时间。在用分治法求解时，有些子问题被重复计算了许多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算。为了达到此目的，可以用一个表来记录所有已解决的子问题的答案。这就是动态规划法的基本思想。
动态规划算法使用于解最优化问题。通常可按以下4个步骤设计：
1、找出最优解的性质，并刻画其结构特征；
2、递归地定义最优值；
3、以自底向上的方式计算出最优值；
4、根据计算最优值时得到的信息，构造最优解。
步骤1~3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省去。若需要求出问题的最优解，则必须执行步骤4。此时，在步骤3中计算最优值时，通常需记录更多的信息，以便在步骤4中，根据所记录的信息，快速构造出一个最优解。
二、0-1背包问题
【问题描述】：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。
【算法分析】：0-1背包问题的最优子结构，设(y1,y2,...,yn)是所给0-1背包问题的一个最优解，则(y2,y3,...,yn)是经过一次选择后的0-1背包问题的最优解。0-1背包问题的递归关系，设当前子问题的最优值为m(i,j)，即m(i,j)使背包容量为j，可选择物品为i,i+1,...,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式：
当i=n时，若j>=wn，则m(i,j)=vn；若0<=j<wn，则m(i,j)=0。
当i<n时，若j>=wi，则m(i,j)=max{m(i+1,j),m(i+1,j-wi)+vi}；若0<=j<wi，则m(i,j)=m(i+1,j)。
【算法实现】Knapsack算法的C++实现如下：
(其中背包信息从文件中读取，点击进入该文件下载界面)
#include "iostream"
using namespace std;
#define n 50 //物品的数量
//物体重量、收益、背包容量
int weight[n], profit[n], contain, x[n], **m;
//从文件中读取背包信息
int read_infor()
{
FILE *fp;
int i;
if ((fp=fopen("knapsack.txt","r"))==NULL)
{
printf("The file is not found!");
return 0;
}
//读取物体收益信息
for(i = 0;i < n;i++)
{
fscanf(fp, "%d", &profit[i]);
}
//读取物体重量信息
for(i = 0;i < n;i++)
{
fscanf(fp, "%d", &weight[i]);
}
//读取背包容量
fscanf(fp, "%d", &contain);
fclose(fp);
return 1;
}
void Knapsack()
{
int jMax = min(weight[n - 1] - 1, contain);
int i, j;
for(j = 0;j <= jMax;j++)
{
m[n - 1][j] = 0;
}
for(j = weight[n - 1];j <= contain;j++)
{
m[n - 1][j] = profit[n - 1];
}
for(i = n - 2;i > 0;i--)
{
jMax = min(weight[i] - 1, contain);
for(j = 0;j <= jMax;j++)
{
m[i][j] = m[i + 1][j];
}
for(j = weight[i];j <= contain;j++)
{
m[i][j] = max(m[i + 1][j], m[i + 1][j - weight[i]] + profit[i]);
}
}
m[0][contain] = m[1][contain];
if(contain >= weight[0])
{
m[0][contain] = max(m[1][contain], m[1][contain - weight[0]] + profit[0]);
}
}
void Traceback()
{
int c = contain;
for(int i = 0;i < n - 1;i++)
{
if(m[i][c] == m[i + 1][c])
{
x[i] = 0;
}
else
{
x[i] = 1;
c -= weight[i];
}
}
x[n - 1] = (m[n - 1][c]) ? 1 : 0;
}
void main()
{
int i, sumWeight = 0;
if(read_infor())
{
m = (int**)malloc(n * sizeof(int*));
for(i = 0;i < n;i++)
{
m[i] = (int*)malloc(contain * sizeof(int));
}
Knapsack();
Traceback();
}
printf("The choice is: \n");
for(i = 0;i < n;i++)
{
sumWeight += weight[i] * x[i];
if(i != 0 && i % 5 == 0)
{
printf(" ");
}
printf("%1d", x[i]);
}
printf("\nThe maximum profit is: %d.", m[1][contain]);
printf("\nThe knapsack weight is %d.\n", sumWeight);
scanf("%d", &i);
for(i = 0;i < n;i++)
{
free(m[i]);
}
free(m);
}
【算法复杂度分析】：从计算m(i,j)的递归式容易看出，上述算法Knapsack需要O(nc)计算时间，而Traceback需要O(n)计算时间。其中，算法Knapsack还存在可以改进的地方，改进算法将在后续的文章中给出。
Resources & Reference:
1、王晓东. 计算机算法设计与分析(第3版) [M]. 北京：电子工业出版社，2009，77-78.
非常谢谢啊！！！受益匪浅啊！！！！
我想请问在knapsack()函数中的倒数四句，为什么不直接放入到前面的循环里面去解决呢？最后的结果就是m[0][jMax]呢！~
m[0][contain] = m[1][contain];
060 if(contain >= weight[0])
061 {
062 m[0][contain] = max(m[0][contain], m[1][contain - weight[0]] + profit[0]);
063 }
应该改为(否则读的有点误导人)
060 if(contain >= weight[0])
061 {
062 m[0][contain] = max(m[1][contain], m[1][contain - weight[0]] + profit[0]);
063 }
@li, 谢谢指正，已经改了。虽然对结果没有影响，但是这样写起来更清楚。
谢谢博主讲解与分享：）
scanf("%d", &i);
for(i = 0;i < n;i++)
{
free(m[i]);
}
free(m);
博主，这个scanf是干啥的啊，，程序运行的时候出现内存报错，，
为什么运行出错呢
这一行：int jMax = min(weight[n - 1] - 1, contain);
出错提示: error C2065: 'min' : undeclared identifier
还有这一行：m[i][j] = max(m[i + 1][j], m[i + 1][j - weight[i]] + profit[i]);
出错提示 : error C2065: 'max' : undeclared identifier
我是新手，请大哥帮忙指示指示，谢谢
第37这一行：int jMax = min(weight[n - 1] - 1, contain);
出错提示：error C2065: 'min' : undeclared identifier
以及第56这一行：m[i][j] = max(m[i + 1][j], m[i + 1][j - weight[i]] + profit[i]);
出错提示：error C2065: 'max' : undeclared identifier
我是新手，请大哥指点指点，非常感谢！
为什么最大是M[1][contain]而不是M[0][contain]?