动态规划

基本思想：

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）

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 
#include 
#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;kh){//该物品太重，无法偷入背包中
        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