动态规划

动态规划的简介

动态规划一般用来解决一些决策问题。给出问题之后通过递推找到问题的最优解。它需要当前问题包含其子问题的最优解。

简单来说

动态规划就是讲问题简化为数列的递推公式，然后用计算机求解。

例如An = An-1 + 2这种形式。在知道A1的情况下， 很容易可以用一个数组的for循环求出An的解

用数组来表示就是A[i] = A[i-1] + 2这个数组的方程也称为状态转移方程 通常情况下会是二维数组

来看个经典的例子——背包问题

有N件物品和一个容量为W的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

先总结一下思路，这题的考虑的量是物品数i、重量W，目标量是价值MAX(V)

在变量确定的情况下得到最高的价值

那么首先的任务就是将C用一个包含V、W信息的数组表示

比如用c[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值

那么可以得到首项c[0][0]=0，c[1][0]=0，c[0][1]=0，接下来就是要找到递推公式使c[N][W]

 for(int i = 1;i <= N;i++)
 {
	 for(int v = 1;v <= W;v++)
	 {
		 if(w[i]>v)
			c[i][v] = c[i-1][v];
		else
		{
			c[i][v] = max(c[i-1][v], c[i][v - w[i]] + v[i]);
		}
	 }
 }