《算法笔记》读书记录DAY

《算法笔记》读书记录DAY CHAPTER_11  提高篇(5)——动态规划

11.7.1 多阶段动态规划问题

有一类动态规划可解的问题，它可以描述成若干个有序的阶段，且每个阶段的状态只和上个阶段有关，一般把这类问题称为多阶段动态规划问题。01背包问题就是个典型的多阶段动态规划问题。

11.7.2 01背包问题

我们来看01背包问题。

题目：

有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品只有1件。其中所有数据都为正整数。

输入样例：

5 8                     // n为5，V为8

3 5 1 2 2            // w[i]

4 5 2 1 3            // c[i]

输出样例：

10

思路：

如果采用暴力算法，每件物品有放和不放两种选择，枚举每种情况时间复杂将达到O(2^n)，这显然不能接受。下面使用复杂度为O(nV)的动态规划做法。

令dp[i][v]表示前 i 件物品(1<=i<=n , 0<=v<=V)恰好装入容量为v的背包中所能获得的最大价值。我们先将整个dp数组初始化为0。考虑对第 i 件物品的选择策略，有两种策略：

（1）不放第 i 件物品，那么问题转化为前 i-1 件物品恰好装入容量为v的背包中所能获得的最大价值，即dp[i-1][v]。

（2）放第 i 件物品，那么问题转化为前 i-1 件物品恰好装入容量为v-w[i]的背包中所能获得的最大价值，即dp[i-1][v-w[i]]+c[i]。

对于第 i 件物品只有这两种策略，且要求获得最大价值，由此写出状态转移方程：

注意到dp[i][v]只与之前的状态dp[i-1][]有关，所以可以枚举 i 从1到n，v 从0到V，通过边界dp[0][v]=0递推出整个数组。实际上每一轮 i 都是对第 i 件物品在不同情形下做出放与不放策略的情况，在枚举完毕后，第n行dp[n][]包含着对n件物品都做出策略后所有的可能情况，其中的最大值即为我们想要的最大价值。

至此，我们已经能够解决问题。时间复杂度和空间复杂度为O(nV)，时间复杂度已达到最优，我们还能继续优化空间复杂度。

如下图，注意到状态转移方程中计算dp[i][v]时总是只需要dp[i-1][v]左侧的部分数据（实际上只有箭头所指的两个数据）。而当计算dp[i+1][]时，只需要dp[i][]的数据，dp[i-1][]已经用不上了。因此不妨直接开一个一维数组dp[v]（即把第一维省去），枚举方向 i 从1到n，v从V到0（逆序），这样状态转移方程变为：

这么处理后，就相当于在二维数组中计算出一行的dp[i][]，就将这行dp[i]存储下来用作dp[i+1][]的计算，同时上一行dp[i-1][]已经被覆盖消除了（因为已经不再需要）。这种做法称为滚动数组。需要注意的是，如果使用二维数组，v从当前行的w[i]枚举到V可以，从V枚举到w[i]也可以。但是如果使用滚动数组，v的枚举必须从V到w[i]，因为这样才能保证当前被覆盖掉的dp[v]不会用作后面的dp[v-1]、dp[v-2]、...、dp[w[i]]的计算。

参考代码：

#include
#include
using namespace std;

const int maxn=100;
const int maxv=1000;

int w[maxn],c[maxn],dp[maxn];

int main() {
	int n,V;
	cin>>n>>V;
	//输入数据 
	for(int i=1;i<=n;i++) {
		cin>>w[i];
	}
	for(int i=1;i<=n;i++) {
		cin>>c[i];
	}
	//初始化边界
	for(int v=0;v<=V;v++) {
		dp[v]=0;
	} 
	//状态转移
	for(int i=1;i<=n;i++) {
		for(int v=V;v>=w[i];v--) {
			dp[v]=max(dp[v],dp[v-w[i]]+c[i]);
		}
	}
	//寻找最大值 
	int ans=0;
	for(int v=0;v<=V;v++) {
		if(dp[v]>ans)
			ans=dp[v];
	}
	cout<

需要注意的是，在4.4小节中我们介绍了贪心算法，有些读者可能会想到用4.4.1节月饼题的贪心解法来解这个题目。实际上这是不可行的，此题是著名的01背包问题，而01背包问题是无法用贪心求解的。无法用贪心的原因在于：本题中，每个物品只有两种选择，要么放入背包要么不放入。当背包所剩空间不足时，本题情形是无法再放入当前物品的，而月饼题可以根据剩余空间放入半斤月饼或是1/3斤月饼来达到最优。

当然，还有一部分背包问题是可以用贪心算法求解的，这需要我们具体问题具体分析。