DP（动态规划）入门

用一道非常经典的例题来引入这个专题。

01背包问题

有n个重量和价值分别为 $w_i$ 和 $v_i$ 的物品。从这些物品中挑选出总重量不超过 $W$ 的物品，求所有挑选方案中总价值和的最大值

限制条件：

$1 \le n \le 100$

$1 \le w_i,v_i \le 100$

$1 \le W \le 10000$

样例输入：

n=4

{w,v}={ (2,3) , (1,2) , (3,4) , (2,2) }

W=5

样例输出：

7（选择0、1、3号物品）

这是被称为背包问题的一个经典问题。联想一下我们之前不久讲过的搜索，我们很容易得到一个dfs的写法。这是一种最朴素的写法，也就是针对每一个物品枚举是否放入背包。这个想法实现后的效果见如下代码：

//输入
int n,W;
int w[N],v[N];

//从第i个物品开始挑选总重小于j的部分所能得到的最大价值 （这是指从物品i 物品i+1 ……物品n-1 中挑选总重小于j的）
int dfs(int i,int j){
  	int res;
  	if(i==n){
      	//已经没有剩余的物品了
      	res=0;
  	}else if(j<w[i]){
      	//空间不够 无法挑选这个物品
      	res= dfs(i+1,j);
  	}else{
      	//即便空间足够 我们也要考虑 挑选和不挑选两种情况
      	res=max( dfs(i+1,j) , dfs(i+1,j-w[i])+j[i] );
  	return res;
}

接着我们来分析一下这个写法的复杂度。这个方法的解答树展开，总共有n层，而且在每一个节点上，都有两个分支，那么最坏需要 $O(2^n)$ 的时间，当n比较大的时候就没有办法解决了。所以要怎么办才好呢？为了优化之前的算法，我们用样例数据来模拟一下我们之前写的这个dfs代码。

DP（动态规划）入门

如图所示，dfs以(3,2)为参数调用了计算了两次。如果参数相同，返回的结果也应该相同，于是第二次调用的时候已经知道了结果却还是白白浪费了计算时间。倘若我们在这里把第一次的计算结果保存记录下来，省略掉第二次以后的重复计算看看。

int dp[N][N];//记忆化数组 用来保存已经有计算结果的函数的返回值

int dfs(int i,int j){
  	if(dp[i][j]>=0){
     	//已经计算过的话 就直接使用之前的结果 
      	return dp[i][j];
    }
  	int res;
  	if(i==n){
      	//已经没有剩余的物品了
      	res=0;
  	}else if(j<w[i]){
      	//空间不够 无法挑选这个物品
      	res= dfs(i+1,j);
  	}else{
      	//即便空间足够 我们也要考虑 挑选和不挑选两种情况
      	res=max( dfs(i+1,j) , dfs(i+1,j-w[i])+j[i] );
  	}
  	return dp[i][j]=res;//把结果记录在数组里
}

int main(){
  	//用-1来表示尚未计算过，初始化整个数组
  	memset(dp,-1,sizeof(dp));
  	printf("%d\n",dfs(0,w));
 	return 0;
}

看起来似乎改的地方不是很多，那么它的复杂度发生了多大的改变呢？对于同样的参数，只会在第一次被调用到执行的时候执行递归的部分，第二次之后都会直接返回。参数的组合不过 $n\times W$ 种，而函数内部之调用两次递归，所以只需要 $O(nW)$ 的复杂度就可以解决这个问题。只需要稍微改良，可以解决的问题的规模就可以大幅度提高。这种方法一般被称为记忆化搜索。

这里介绍一下memset函数。memset是按照1字节为单位对内存进行填充，-1的每一位二进制都是1，0的每一位二进制都是0，所以可以-1和0可以使用memset快速对数组进行初始化，但必须要注意，像是1、2之类的数字就没有办法通过memset进行初始化了。

接下来我们来研究一下前面记忆化搜索中用到的记忆化数组。记 $dp[i][j]$ 为从第i个物品开始挑选总重小于j的物品，总价值的最大值。于是我们有如下的递推式：
$dp[n][j]=0$

$dp[i][j]= \begin{cases} dp[i+1][j] &\text{(j<w[i])} \\ max(dp[i+1][j] , dp[i+1][j-w[i]]+v[i]) &\text{(其他)} \end{cases}$

DP（动态规划）入门

如上图所示，不写递归函数，直接利用递推式将各个项的值计算出来，简单地利用二重循环也可以解决上述问题。

int dp[N][N];//dp数组

int main(){
  
  		for(int i=n-1;i>=0;i--){
          	for(int j=0;j<=W;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]);
              	}
          	}
  		}
  		printf("%d\n",dp[0][W]);
  		return 0;
}

这个算法的复杂度显然也是 $O(nW)$ 但是相比前面简洁了很多。以这种方式一步步按顺序求出问题的解地方法被称作是动态规划，也就是dp。解决问题时，可以采用从记忆化搜索出发推导出递推式，熟练以后也可以直接得出递推式。

这里再推荐两篇简单介绍dp的文章。

https://blog.****.net/HFUTLXM/article/details/78959012

https://blog.****.net/lzw66666/article/details/78963448

post by Yummy

DP（动态规划）入门

DP（动态规划）入门

01背包问题

限制条件：

样例输入：

样例输出：

相关推荐