动态规划（一）——背包问题

发表于 | 分类于 |
字数统计 1,720 | 阅读时长 7

简介

动态规划是一种特殊的算法技巧，它通过把原问题分解为相对简单的子问题的方式来求解复杂问题。
动态规划中，子问题的解被称为状态，状态之间的转换称作状态转换方程。动态规划的核心就是找到状态及状态转换方程。
下面通过动态规划的实例——背包问题，来阐述其方法。

背包问题

问题简述

有一个人，他背上一个背包去森林里寻宝，发现一堆宝石，但是他的背包容量有限，无法一次装下所有宝石。假设背包容量为capacity，如果把宝石编号为1，2，…，n，宝石的体积分别为volume[0]，volume[1]，…，volume[n-1]，宝石的价值依次为value[0]，value[1]，…，value[n-1]。现在问题来了，这个人如何挑选宝石放进背包，可以使自己获得最大利益？

问题分析

这是一个典型的动态规划问题。我们不妨先来假设一下，假设背包容量为10，宝石的体积为5，4，3，宝石的价值为20，10，12。
如果什么都不想，直接排列组合，也是可以的。对于每一个宝石，有两种选择，放入背包，或者不放入背包。这样一共有8种情况，只需再考虑每种情况下背包的容量问题，然后得出最大价值即可。
这种方法的劣势在于需要计算所有的情况，有些明显不符合的情况也需要判断。比如，所有宝石都不放，或者所有宝石都放入的情况，应该是可以直接跳过不考虑的。
那么，有没有比这个简单，或者说，效率更高的方法？答案就是动态规划。
前面提到，动态规划的核心在于找到状态及状态转移方程。我们不妨试着来找一下。
首先，状态很容易找到。我们先从简单的情况着手。第一次，把前一个宝石放入背包，得到最大价值20；第二次，把前两个宝石放入背包，得到最大价值30；第三次，把前三个宝石放入背包，得到最大价值32。是不是发现什么规律？对！他们可以统一表示，如果把maxValue[i][j]定义为将前i个宝石放入容量为j的背包可以得到的最大价值，那么上述三次操作可以表示为：maxValue[1][10]=20，maxValue[2][10]=30，maxValue[3][10]=32。这些都是我们要找的状态，当然，这些也只是其中的一部分状态。
下面，我们找状态转移方程，即从前一个状态，转移到后一个状态所经历的变化过程。我们不妨从后往前推，找从后一个状态，转移到前一个状态经历的变化。要得到maxValue[3][10]，有两种情况，即第三个宝石放入和不放入的情况。若第三个宝石不放入背包，则maxValue[3][10]=maxValue[2][10]；若第三个宝石放入背包，可以得到maxValue[3][10]=maxValue[2][10-3]+12=maxValue[2][7]+12。综上，maxValue[3][10]=max{ maxValue[2][10], maxValue[2][7]+12 }。问题便转换为求前一个状态maxValue[2][10]与maxValue[2][7]的值。接着，再经过一步一步的转换，最终化繁为简，转换到初始状态，并解决问题。
下面，我们用过代码实例（Java实现）来具体阐述。我们会用递归方法与非递归方法解决之，由于个人感觉递归方法较易理解，故先讲述递归方法。

递归方法

递归方法与分析的过程一致，从后往前推导，逐步得到最大价值。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 返回前number个宝石放入容量为capacity的背包可以获得的最大价值
public int knapsackProblemRecursive(int[] volumes, int[] values, int number, int capacity) {
	// number从1开始，如果number为0时，可以获得的最大价值为0
	if (number == 0) return 0;
	// 判断第number个宝石是否放入
	// 第number个宝石不放入背包，计算最大价值
	int notAdded = knapsackProblemRecursive(volumes, values, number-1, capacity);
	// 第number个宝石放入背包，计算最大价值
	int added = 0;
	// 放入背包前确保有足够空间
	if (capacity >= volumes[number-1]) {
		added = knapsackProblemRecursive(volumes, values, number-1, capacity-volumes[number-1]) + values[number-1];
	}
	return notAdded > added ? notAdded : added;
}

非递归方法

非递归方法参考了Hawstein博客中的方法，使用二维数组存储各个状态下的最大价值，即局部最优解，最后得到全局最优解。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 返回前number个宝石放入容量为capacity的背包可以获得的最大价值
public static int knapsackProblemNonRecursive(int[] volumes, int[] values, int number, int capacity) {
	// maxValues[i][j]: 前i个宝石装入剩余容量为j的背包中的最大价值
	int[][] maxValues = new int[100][100];
	for (int i = 0; i <= number; i++) {
		for (int j = 0; j <= capacity; j++) {
			// number从1开始，前0个宝石放入背包，最大价值均为0
			// 第i个宝石不放入背包，计算最大价值
			maxValues[i][j] = i==0 ? 0 : maxValues[i-1][j];
			// 确保有足够空间放入宝石
			if (i > 0 && j >= volumes[i-1]) {
				// 第i个宝石放入背包，计算最大价值
				int added = maxValues[i-1][j-volumes[i-1]] + values[i-1];
				maxValues[i][j] = maxValues[i][j] > added ? maxValues[i][j] : added;
			}
		}
	}
	// 返回要求计算的最大价值
	return maxValues[number][capacity];
}

完全背包问题

上述问题是基本的01背包问题，另一个基本的背包问题模型，是完全背包问题。完全背包问题与01背包问题的区别在于，每一种物品都有无数个，而不是只有一个。我们仍可以按照01背包问题的方法来分析，这次maxValue[i][j]是找出前i个宝石放入容量为j的背包，每个宝石可以放0个、1个、2个、3个……我们可以发现对于每一种宝石i，能够放入背包的最大量为capacity/volume[i]。于是，我们写出状态转移方程为maxValue[i][j]=max{ maxValue[i-1][j-k*volume[i]]+k*value[i] | 0 <=k<=capacity/volume[i] }，然后根据状态转移方程进行实现即可。

多重背包问题

多重背包问题与完全背包问题的不同在于前者在宝石数量上作了限制，给出每种宝石的数量n[i]。多重背包问题可以看作是完全背包问题的简化，即我们不需要计算每一种宝石最多可以放几个，而由题目给出。同样，我们给出状态转移方程maxValue[i][j]=max{ maxValue[i-1][j-k*volume[i]]+k*value[i] | 0 <=k<=n[i] }。

参考资料

动态规划之背包问题（一）
背包问题九讲

坚持原创技术分享，您的支持将鼓励我继续创作！