动态规划
基本思想：
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）
01背包问题
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi∈ (0,1)，此问题称为0-1背包问题。
数据：物品个数n=5,物品重量W[6]={ 0 , 2 , 3 , 4, 5 , 9 };物品价值V[6]={ 0 , 3 , 4 , 5 , 8 ,10 };背包容量为C=20。
B(K,h) :K表示前K个物品，h表示现在剩下的背包空间
B（2,20）表示偷0.1.2个物品时（不是说所有的都偷）背包剩余的空间容量为20，其B(2,20)的值表示所偷物品的价值。
B（K,h）的取值分两种情况：
1、当第K个的重量超过剩余空间时，B（K,h）=B(K-1,h)
2、当第K个的重量不超过剩余空间时，有两种情况：
(1)选择偷入背包中：B（K,h）=B(K-1,h-Wk)+Vk
(2)选择不偷入背包中：B（K,h）=B(K-1,h)。
下图表示一个在线0-1背包问题的表示：
代码为：
#include <stdio.h>
#include <stdlib.h>
#define N 6
#define M 21
int B[N][M]={0};
int W[6]={0,2,3,4,5,9};
int V[6]={0,3,4,5,8,10};
void knapsack(){
int k,h;
for(k=1;k<N;k++)
for(h=1;h<M;h++){
if(W[k]>h){//该物品太重，无法偷入背包中
B[k][h]= B[k-1][h];
}
else{
int value1=B[k-1][h-W[k]] +V[k]; //要偷入背包中
int value2=B[k-1][h];//不偷入背包
if(value1>value2){//比较是否要偷入背包中
B[k][h]=value1;
}
else{
B[k][h]=value2;
}
}
}
}
int main()
{
knapsack();
printf("%d\n",B[5][20]);//20表示背包的容量
return 0;
}
视频讲解地址：http://video.tudou.com/v/XMTc5MjQ3NTg5Mg==.html?__fr=oldtd