动态规划讲解

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

其核心思想就是利用已知的信息解决问题。

其中比较经典的问题就是背包问题，分为有限背包问题和无限背包问题，这里我们用有限背包(也叫01背包)   说明动态规划思想：

01背包：一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？

如果采用暴力穷举的方式，每件物品都存在装入和不装入两种情况，所以总的时间复杂度是O(2^N)，这是很不好的。我们可以怎样进行优化？

我们可以想一下，如果背包只能装1kg时，我们肯定知道最大价值是2，因为它只能存下两种物品，而且最大价值是2。

这是我们可以对背包进行递加，如果它有2kg的容量呢，这时我们就多了一个空间。

显然，这时有三种选择：

        要么放入剩下的1kg的物品，则剩余1空间。

        要么放入剩下的2kg的物品，剩余0空间。

        要么不放入。

对于这三种选择，我们可以用一个状态表达式：

        val(weight) = max(val(weigth-1)，val(weight-剩下)+val(剩下))

用一个状态来标记它是否被装入，便可以实现它的代码。

#include
using namespace std;
#include 
 
int main()
{
	int w[5] = { 0 , 2 , 3 , 4 , 5 };			//商品的体积2、3、4、5
	int v[5] = { 0 , 3 , 4 , 5 , 6 };			//商品的价值3、4、5、6
	int bagV = 8;					        //背包大小
	int dp[5][9] = { { 0 } };			        //动态规划表
 
	for (int i = 1; i <= 4; i++) {
		for (int j = 1; j <= bagV; j++) {
			if (j < w[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
 
	//动态规划表的输出
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 9; j++) {
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}
 
	return 0;