动态规划算法

1. 背包问题

1.1 01背包问题

约束条件是：给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。

题目链接

典型的01背包问题。骨头的数量已知，接下来又知道了每个骨头的价值和体积，这就相当于每种物品只有一个，对每种物品只需考虑选与不选两种情况。并且，体积的限制是不能超过背包的容积V。很容易想到以下做法：

//定义状态dp[i][j]表示前i个物品所占的体积为j，dp[i][j]中记录这个状态能够取得的最大值。
//w[i]表示物品价值，v[i]表示物品体积
//状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
#include <iostream>
#include <string.h>
using namespace std;

const int maxn = 1005;
int w[maxn], v[maxn], dp[maxn][maxn];

int main(){
	int T, N, V;
	cin >> T;
	while(T--){
		cin >> N >> V;
		int i, j;
		for(i = 1; i <= N; i++) cin >> w[i];
		for(i = 1; i <= N; i++) cin >> v[i];
		memset(dp, 0, sizeof(dp));
		for(i = 1; i <= N; i++){
			for(j = 0; j <= V; j++){  //注意：V可以为0。
				if(j >= v[i])
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
				else
					dp[i][j] = dp[i - 1][j];
			}
		}
		cout << dp[N][V] << endl;
	}
	return 0;
}

上述做法的确AC了。但是，这里的N，V最大只有1000，一旦变得更大了，开一个dp的二维数组显然是行不通的。是时候上滚动数组了。

/*
首先，我们发现dp[i][j]只与dp[i-1][j]和dp[i-1][j-v[i]]有关。也就是说，前i个物品所占体积只与前i-1个物品有关。而一旦计算了第i行所有的dp[i][j]，那么第i-1行就没有作用了，因为每一行只会参考其上一行的dp[i][j]。
于是，对于dp[i-1][j]，如果能够通过dp[i][k](k>=j)已经被计算就可知dp[i-1][j]的值将不再被使用，那么就将dp[i][j]存在
dp[i-1][j]中。这时令j从V到0递减，将dp[i][j]的值覆盖dp[i-1][j]即可。
所以，dp转化为了一维数组。
*/
#include <iostream>
#include <string.h>
using namespace std;

const int maxn = 1005;
int w[maxn], v[maxn], dp[maxn];

int main(){
	int T, N, V;
	cin >> T;
	while(T--){
		cin >> N >> V;
		int i, j;
		for(i = 1; i <= N; i++) cin >> w[i];
		for(i = 1; i <= N; i++) cin >> v[i];
		memset(dp, 0, sizeof(dp));
		for(i = 1; i <= N; i++)
			for(j = V; j >= v[i]; j--)
				dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
		cout << dp[V] << endl;
	}
	return 0;
}

1.2 完全背包问题

基本概念：与01背包不同的是，完全背包中每种物品的数量没有限制，可以无限使用。状态定义与01背包一致。

题目链接

已知硬币总重量，每种硬币的重量和面值，求硬币面值之和最小的可能值。

/*
状态转移方程：dp[i][j] = min(dp[i-1][j-n*v[i]] + n*w[i]), 0 <= n*v[i] <= j.
空间优化后：dp[j] = min(dp[j-n*v[i]] + n*w[i]), 0 <= n*v[i] <= j.
改进后：d[j] = min(dp[j], dp[j-v[i]] + w[i]), j >= v[i].
*/
#include <iostream>
#include <string.h>
using namespace std;

const int maxn = 10005;
int dp[maxn];

int main(){
	int T, P, W, E, F, N;
	cin >> T;
	while(T--){
		cin >> E >> F;
		int V = F - E;
		cin >> N;
		memset(dp, -1, sizeof(dp));  //初始化为-1，-1表示状态未到达
		dp[0] = 0;  //当下面循环中j = 0时，可以使得dp[W] = P。
		int i, j;
		for(i = 1; i <= N; i++){
			cin >> P >> W;
			for(j = 0; j <= V - W; j++){
				if(dp[j] == -1) continue;  //状态未达到，不能参考这个状态
				else if(dp[j + W] == -1) dp[j + W] = dp[j] + P;  //加上{P, W}这种情况的状态还未达到，就进行转移
				else dp[j + W] = min(dp[j + W], dp[j] + P);  //这种状态已经达到了，就取较小的
			}
		}
		if(dp[V] == -1)  //说明任何硬币组合都不能达到V的状态
			cout << "This is impossible." << endl;
		else
			cout << "The minimum amount of money in the piggy-bank is " << dp[V] << "." << endl;
	}
	return 0;
}

1.3 多重背包问题

基本概念：多重背包的特点是物品的数量可以大于1但有限制。状态定义与01背包一致。

题目链接

已知手表价格大于0且不超过M，有N种硬币，已知每种硬币的价值和数量，求能用硬币支付的手表价格的情况有多少种。

//定义dp[i]为是否可以使面值之和为i。
//处理每种硬币时，转移次数与Ci有关，使得处理第i种硬币的复杂度是O(M*Ci)，而当Ci较大时，复杂度较高。
/*
可以用二进制的方法优化，使得每种物品的转移次数变为O(M*log(Ci))，方法是将i种硬币分组，分别以1,2,4,...,2的n次方个硬币为一组，这些数相加等于Ci。可知，任意小于等于Ci的数都可以用这些数中的一部分(或全部)之和表示出来。将每一组的硬币面值相加作为一个硬币来处理，就可以转化为01背包问题来解决了。
*/
#include <iostream>
#include <string.h>
using namespace std;

int dp[100005], a[105], c[105], w[1005];

int main(){
	int n, m;
	while(cin >> n >> m && (n || m)){
		memset(dp, 0, sizeof(dp)); dp[0] = 1;
		int i, j;
		for(i = 1; i <= n; i++)
			cin >> a[i];
		for(i = 1; i <= n; i++)
			cin >> c[i];
		int cnt = 0;
		for(i = 1; i <= n; i++)
			for(j = 1; c[i] > 0; j *= 2){  //对每种硬币进行分组，用j模拟2的幂(也可用移位，j <<= 1)
				int t = min(j, c[i]);  //若c[i]并不刚好是等比数列之和，那么多出来的部分小于j，这里考虑的是最后的情况
				c[i] -= t;
				w[cnt++] = a[i]*t;  //记录该分组的硬币价值之和
			}
		int ans = 0;
		for(i = 0; i < cnt; i++)
			for(j = m; j >= w[i]; j--)
				if(dp[j-w[i]])
					dp[j] = 1;
		for(i = 1; i <= m; i++)
			ans += dp[i];
		cout << ans << endl;
	}
	return 0;
}

2. 状态压缩

2.1 旅行商问题

题目链接

访问N座城市，共有M条路，必须访问所有的城市至少一次，并且访问次数不能超过两次(也就是1次或2次)。已知每条道路的费用，求最小费用，若不能完成就返回-1.

//
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

int dp[60000][11], c[20][20], len[11];
#define Gets(i, j) (i/len[j])%3

int main(){
	len[0] = 1;
	for(int i = 1; i <= 10; i++)
		len[i] = len[i-1] * 3;
	int n, m, f, a, b, w, u, v, ans;
	while(~scanf("%d%d", &n, &m)){
		memset(c, 0x3f, sizeof(c));
		memset(dp, 0x3f, sizeof(dp));
		for(int i = 0; i < m; i++){
			scanf("%d%d%d", &a, &b, &w);
			a--; b--;
			c[a][b] = c[b][a] = min(c[a][b], w);
		}
		ans = dp[0][0];
		int i, j;
		for(i = 0; i < n; i++)
			dp[len[i]][i] = 0;
		for(i = 1; i < len[n]; i++){
			f = 1;
			for(j = 0; j < n; j++){
				if(Gets(i, j)==0){
					f = 0;
					continue;
				}
				for(int v = 0; v < n; v++){
					if(Gets(i, v)==2)
						continue;
					u = i + len[v];
					dp[u][v] = min(dp[u][v], dp[i][j] + c[j][v]);
				}
			}
			if(f){
				for(j = 0; j < n; j++)
					ans = min(ans, dp[i][j]);
			}
		}
		if(dp[0][0]==ans) ans = -1;
		printf("%d\n", ans);
	}
	return 0;
}

2.2 插头dp

基本概念：插头dp也是状态压缩dp的一种，成为轮廓线dp。通常用于解决二维空间上的状态压缩问题，且约束条件是每个位置只需要关心与自己邻近的几个点。所以，应该按顺序逐个位置进行处理。

题目链接

3. 动态规划优化

3.1 数据结构优化

3.2 斜率优化

3.3 四边形不等式优化

4. 常见动态规划题目类型

4.1 树形dp

4.2 RMQ问题

4.3 有向图最短路

4.4 最长上升子序列

5. 习题解析的博客链接