算法(七)：图解动态规划

动态规划，将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法

与贪婪算法区别

• 2者都是将大问题划分为规模更小的子问题

• 动态规划实质是分治法以及解决冗余，将各个子问题的解保存下来，让后面再次遇到的时候可以直接引用，避免重复计算，动态规划的显著特征之一，会有大量的子问题重复，可以直接使用前面的解

• 贪心算法的每一次操作都对结果产生直接影响(处理问题的范围越来越小)，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能(比如背包问题，同一列相同容量的小背包越往后才是最优解，推翻前边的选择)。动态规划主要运用于二维或三维问题，而贪心一般是一维问题

• 贪婪算法结果是最优近似解，而动态规划是最优解

• 动态规划类似搜索或者填表的方式来，具有最优子结构的问题可以采用动态规划，否则使用贪婪算法

案例

这边的案例来自"算法图解"一书

案例一

背包问题：有一个背包，容量为4磅 ， 现有如下物品

要求达到的目标为装入的背包的总价值最大，并且重量不超出。

类似问题在前边""贪婪算法"一文介绍了求出近似解，现在使用动态规划求出最优解。

解决类似的问题可以分解成一个个的小问题进行解决，假设存在背包容量大小分为1，2，3，4的各种容量的背包(分配容量的规则为最小重量的整数倍)：

例如:

对于第一行(i=1), 目前只有吉他可以选择，所以

对于第二行(i=2),目前存在吉他和音响可以选择,所以

对于第三行(i=3),目前存在吉他和音响、电脑可以选择,所以

以上的都符合公式:

F(i,j) = max{ F(i-1,j), W(i) + F(i,j = j-V(i))} 
即max{上面一个单元格的值, 当前商品的价值 + 剩余空间的最大价值}

F(i,j)的代表 i行j列可以获得的最大价值，W(i)代表该行物品的价值,V(i)在此处代表该行物品所占据的空间重量,
F(i,j = j-V(i)) : 假设
复制代码

比如F(3,4) = max{ F(2,4), F(3,3) + 2000 } = max { 3000, 1500 + 2000} = 3500, 该问题的时间复杂度O(V*N),V位背包容量，N为物品总数，即表格格子总数。

上述背包空间的划分依据一般根据最小的物品所占的大小整数倍进行划分(这边是吉他，占据1磅)，假设多了个0.5磅的东西则，需要划分为更细的粒度(0.5,1,1.5,2,2.5,3,3.5,4)

并且会发飙沿着一列往下走时，最大价值不会降低，因为每次计算迭代时，都选取的最大值。并且结果与行的顺序并无关系，比如更换为:

使用上述公式计算，当背包为4磅，可装入的最大价值依旧为 3500:

计算过程:

i=1:(1,1)、(1,2)、(1,3) : 因为 j=1,2,3时 < (V(i) = 4) 所以装不下，置空 (1,4) : max{ F(i-1,j), W(i) + F(i,j-V(i))} = max{ F(0,4),3000 + F(1,0)} = 3000

i=2:(2,1)、(2,2) : 因为 j=1,2时 < (V(i) = 4、V(i-1)=3) 所以装不下，置空 (2,3): max{ F(1,3), W(2) + F(2,0)} = 2000 (2,4): max{ F(1,4), W(2) + F(2,1)} = max{ 3000, 2000 + 0} = 3000

i=3:(3,1) : max{ F(2,1), 1500 + F(3,0)} = 1500 (3,2) : max{ F(2,2), 1500 + F(3,1)} = 1500 (因为吉他只有一把，无法重复放入) (3,3) : max{ F(2,3), 1500 + F(3,2)} = max{2000,1500} = 2000 (因为吉他只有一把，无法重复放入) (3,4) : max{ F(2,4), 1500 + F(3,3)} = max{3000,3500} = 3500

案例二

旅游行程最优化:

假设有2天的时间，想要去如下地方旅游，如何好好利用，使得总评分高:

该问题其实也是一个背包，只是容量变成了时间，处理方式同上，很快便可以得出:

F(i,j) = max{ F(i-1,j), W(i) + F(i,j-V(i))} 即max{上面一个单元格的值, 当前商品的价值 + 剩余空间的价值}

F(i,j)的代表 i行j列可以获得的最大价值，W(i)代表该行物品的价值,V(i)在此处代表该行物品所占据的空间重量
复制代码

局限性

动态规划的局限性之一便是每次处理时，考虑的是整件物品进行处理，无法支持拿走几分之几的做法,比如案例一修改为:

背包4磅，1.有一整袋10磅的燕麦，每磅6美元 ； 
                 2.有一整袋10磅的大米，每磅3美元 ； 
                 3.有一整袋10磅的土豆，每磅5美元 ； 
        
        因为整袋无法装入，情况不再是要么拿要么不拿，而是打开包装拿物品的一部分，这种情况下动态规划就无法处理。动态规划只适合于整件物品处理的情况。但使用前面介绍的贪婪算法则很合适，一个劲拿最贵的，拿光后再拿下一个最贵。
复制代码

动态规划的局限性之二便是无法处理相互依赖的情况，比如案例二中，增加想要去的3个地点

从这些地方还需要很长时间，因为得从伦敦前往巴黎，这需要0.5天时间（1.5天包含了0.5天的路程消耗）。如果这3个地方都去的话，是总的需要1.5 * 3= 4.5天？ 其实并不是，到达巴黎后，连续玩这3个地方其实只需 1.5 + 1 + 1 = 3.5天。 这种将 "巴黎铁塔"装入"背包"会使得"巴黎大学"、"巴黎医院"变便宜的情况，无法使用动态规划来进行建模。
复制代码

动态规划功能虽然强大，能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的，即不依赖于其它子问题时，动态规划才管用。

java实现

案例一：

/**
 * 动态规划 - 简单背包问题
 * @author Administrator
 *
 */
public class KnapsackProblem {
	
	public static void main(String[] args){

		float knapsackWeight = 4;
		float[] itemsWeights = new float[] {1, 4, 3};
		float[] itemsPrices = new float[] {1500, 3000, 2000}; 
		float[][] table = knapsackSolution(knapsackWeight, itemsWeights, itemsPrices);
		
		for (int line = 0; line < table.length; line++ ) {
			System.out.println("-----------------line =" + line);
			for (int colume = 0; colume < table[line].length; colume++ ) {
				System.out.println(table[line][colume] + ",");
			}
		}
	}
	
	/**
	 * 
	 * @param knapsackWeight 背包总容量
	 * @param itemsWeights	  各个物品的所占据的容量
	 * @param itemsPrices	  各个物品所具有的价值	
	 * @return
	 */
	public static float[][] knapsackSolution(float knapsackWeight, float[] itemsWeights, float[] itemsPrices) {
		if (itemsWeights.length != itemsPrices.length) {
			throw new IllegalArgumentException();
		}
		
		//计算表格的行数 --物品数量
		int lines = itemsPrices.length;
		//计算出划分的背包最小的空间，即表格每一列代表的重量为  column * minWeight
		float minWeight = getMinWeight(itemsWeights);
		//计算表格的列数 --分割出的重量数目
		int colums = (int) (knapsackWeight/minWeight);
		System.out.println("lines = " + lines + ",colums = " + colums + ",minWeight = " + minWeight);
		//创建表格对象,lines行colums列
		float[][] table = new float[lines][colums];
	
		for (int line = 0; line < lines; line++ ) {
			for (int colume = 0; colume < colums; colume++ ) {
				
				float left = table[(line - 1) < 0 ? 0 : (line - 1) ][colume];
				float right = 0;
				//判断当前划分的小背包是否可以装下该物品，当前背包容量为(colume +1)*minWeight
				if ((colume +1)*minWeight >= itemsWeights[line]) {
					//获取当前背包剩余空间
					float freeWeight = ((colume+1)*minWeight - itemsWeights[line]);
					//判断剩余空间是否还可以装下其它的东西
					int freeColumn = (int) (freeWeight/minWeight) - 1;
					if (freeColumn >= 0 && line > 0) {
						//因为表格上同一列的位置上，越往下价值越高，所以这边直接取的上一行的freeColumn位置就行
						right = itemsPrices[line] + table[line - 1][freeColumn];
					}else {
						right = itemsPrices[line];
					} 	
				}

				table[line][colume] = Math.max(left, right);
			}
			
		}
		return table;
		
	}
	
	/**
	 * 获取所有物品中最小的重量
	 * 
	 * @param itemsWeights 各个物品的所占据的容量
	 * @return
	 */
	public static float getMinWeight(float[] itemsWeights) {
		float min = itemsWeights[0];
		
		for (float weight : itemsWeights) {
			min = min > weight ? weight : min;
		}
		//保留最多2位小数，并默认非零就进位1.222 --> 1.23
		//为啥String.valueOf，参照https://www.cnblogs.com/LeoBoy/p/6056394.html
		return new BigDecimal(String.valueOf(min)).setScale(2, RoundingMode.UP).floatValue();
	}
	
}
复制代码

执行完main方法打印信息如下:
lines = 3,colums = 4,minWeight = 1.0
-----------------line =0
1500.0,
1500.0,
1500.0,
1500.0,
-----------------line =1
1500.0,
1500.0,
1500.0,
3000.0,
-----------------line =2
1500.0,
1500.0,
2000.0,
3500.0,
复制代码

简单修改为，即为案例二的实现代码： float knapsackWeight = 2; float[] itemsWeights = new float[] {0.5f,0.5f,1,2,0.5f}; float[] itemsPrices = new float[] {7,6,9,9,8};