动态规划（Java）

发表于 | 分类于

动态规划（Java）

动态规划是经典的算法问题，也是常考问题。而背包问题又是其经典的例子，动态规划主要在于递推方程的建立。

背包问题主要分为01背包，完全背包，多重背包。

这里将分别研究这三种类型，也结合了一些别人的博客，并争取用通俗易懂的方式来解释下。

2017年09月27日，备注：目前只完成01背包问题的整理。

背景

（仅仅是为便于理解算法）

小偷窃入一家金店，发现有若干种金子，每种金子的重量不一样，不同质量的金子的价值也不一样。可能是轻的价值高，有的确实是重的价值高。小偷的书包容量能承受的重量有限，问如何装配才能使所掠走的金子价值最大？

01背包

给定N种物品和一个已知容量的背包。物品i的重量是Wi，其价值位Vi ，背包的容量为C。现在每种物品有且只有一个。问应该如何选择装入背包的物品，才能使装入背包的物品的总价值最大？

背景分析

1）首先最关键的一点是，01背包是指装入的物品要么全装入要么全不装入，或者也可以理解为每种物品只有一个。

2）动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

3）动态规划如果要求得最优解，则第i步的之前所有i-1步的结果是最优的。即局部最优到整体最优。

4）用蛮力法（暴力循环）也是可以解决此类问题，蛮力法可以解决大多数的算法问题，但是对于数量较大时的问题解决耗时太长。动态规划效率为线性，蛮力法效率为指数型。

递推方程

使用V(i,j)来表示放入i个物品，已有重量为j时的总价值。

分析将物品放入背包的过程，存在以下的情况：

1）如果背包的剩余重量已经不足以放的下第i个物品，那么有：

V(i,j)=V(i-1,j)。

2）如果背包的剩余重量能够放入第i个物品，那么此时可以选择放入这个物品，也可以选择不放入这个物品。

此时有：

a）如果放入了这个物品，那么此时的书包内的物品总价值为没有放入这个物品之前i-1个物品的总价值加上这个物品的价值，即：

V(i,j)=V(i-1,j-Wi)+Vi

b）如果没有放入这个物品，那么此时的书包内的物品总价值不变：

V(i,j)=V(i-1,j)

实现过程

首先建立如下的表：

背包的最大的容量为10。

image

已知物品的重量和价值，求解在不同的背包容量下的背包中能存放的最大价值和具体的物品。

为什么要求解最大容量为1~9的情况呢？因为可以根据这些之前的情况来回溯求得最大时的所放的具体物品。

如果不需要回溯求解的话，那么使用一维数组直接求解容量为10时的最大就行了。

这里的填表时是从左向右，从下向上。当然也可以从左向右，从上向下。

表中填写的值是背包中的最大价值。

填完表后的情况如下：

image

下面选择几个来讲解一下：

i）单元格E5的值。背包的总容量（最大承受重量）为2。
如果不用上面的递推规则，则手动观察可以有：物品名为c,d,e的重量均大于2，所以一个都不能放入，能放入的价值总和为0；
如果使用上面的递推规则：
放入第i个物品，超出书包的剩余容量，所以V(i,j)=V(i-1,j)，而V(i-1,j)为0，所以此时V(i,j)=0；

ii）单元格K3的值。背包的总容量（最大承受重量）为8。
如果不用上面的递推规则，则手动观察可以有：最大的价值是a,b,e，有W(X1,X2,X5)=2+2+4=8，V(X1,X2,X5)=6+3+6=15；
如果使用上面的递推规则：
放入第i个物品，可以未超过书包的剩余容量， 所以有两种情况：
a) 第i个物品放入，第i个物品为a，则V(i,j)=V(i-1,j-Wi)+Vi=V(i-1,8-2)+6=V(5-1,6)+6=V(4,6)+6=9+6=15；
b) 第i个物品未放入，则V(i,j)=V(i-1,j)=9；
两者取最大，则V(i,j)=15。

有了上面的表格，也能轻松找到总容量最大的情况。那么怎么找到容量最大时的具体装包方案呢？或者任意方案的具体安排？

这里采用另一个博客的截图，能更好的说明这个解决方法，不过填表方式是从上而下，从左到右：

image

image

根据填表的递归方程可以有如下的寻解方式：

1） V(i,j)=V(i-1,j)时，说明没有选择第i个商品，则回到V(i-1,j)；

2） V(i,j)=V(i-1,j-w(i))+v(i)时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回溯到装该商品之前，即回到V(i-1,j-w(i))；

3） 一直遍历到i＝0结束为止，所有解的组成都会找到。

如上例子，

1） 最优解为V(4,8)=10，而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10，所以第4件商品被选中，并且回溯到V(3,8-w(4))=V(3,3)；

2） 有V(3,3)=V(2,3)=4，所以第3件商品没被选择，回溯到V(2,3)；

3） 而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4，所以第2件商品被选中，并且回溯到V(1,3-w(2))=V(1,0)；

4） 有V(1,0)=V(0,0)=0，所以第1件商品没被选择；

现在再来看看本文的例子，挑选一个M3，为15。
1）V(5,10)=15 != V(4,10)=11 ，却有 V(5,10)=V(4,10-W5)+V5=V(4,8)+6=15，所以a被选中，并回溯到V(4,8)；
2）V(4,8)=9 != V(3,8)=6，却有 V(4,8)=V(3,8-W4)+V4=V(3,6)+3=6+3=9，所以b被选中，并回溯到V(3,6)；
3) V(3,6)=6 == V(2,6)=6，继续回溯到V(2,6)；
4）V(2,6)=6 == V(1,6)=6，继续回溯到V(1,6)；
5）V(1,6)已经到底，所以e被选中。
所以最后的具体放置方案是：15=6+3+6，即abe。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package com.chain.blog.test.day05;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class FullPackTest {

	public static void main(String[] args) {
		test1();
	}

	private static int m;
	private static int n;
	private static int[] w;
	private static int[] v;
	private static int[][] t;

	private static void test1() {
		try (Scanner in = new Scanner(System.in)) {
			// 背包的最大承受质量
			m = in.nextInt();
			// 物品的数量
			n = in.nextInt();
			// 物品的重量
			w = new int[n];
			// 物品的价值
			v = new int[n];
			for (int i = 0; i < n; i++) {
				w[i] = in.nextInt();
			}
			for (int i = 0; i < n; i++) {
				v[i] = in.nextInt();
			}
			t = new int[n][m];
			process();
			print();
			detail();
		}
	}

	private static void detail() {
		// 在背包最大可承载质量下的最大可装载的价值为有上角的值
		int maxValue = t[0][m - 1];
		List<Integer> maxDetail = new ArrayList<>();
		road(maxDetail, 0, m - 1);
		System.out.println("the bag max value: " + maxValue);
		System.out.println("the bag now weight: " + sum(maxDetail));
		System.out.println("the detail: " + maxDetail);
	}

	private static long sum(List<Integer> list) {
		long sum = 0;
		for (Integer i : list) {
			sum += w[i - 1];
		}
		return sum;
	}

	private static void road(List<Integer> list, int i, int j) {
		while (true) {
			if (V(i, j) == 0)
				return;
			if (V(i + 1, j) != V(i, j))
				break;
			else
				i++;
		}

		list.add(i + 1);

		road(list, i + 1, j - w[i]);
	}

	private static void process() {
		for (int j = 0; j < m; j++) {
			// j+1即是书包承受的最大重量
			for (int i = n - 1; i > -1; i--) {
				if (w[i] > j + 1) {
					t[i][j] = V(i + 1, j);
				} else {
					int nput = V(i + 1, j);
					int put = V(i + 1, j - w[i]) + v[i];
					t[i][j] = nput > put ? nput : put;
				}
			}
		}
	}

	private static int V(int i, int j) {
		if (i < 0 || j < 0 || i > n - 1 || j > m - 1)
			return 0;

		return t[i][j];
	}

	private static void print() {
		System.out.print("序号\t重量\t价值\t");
		for (int i = 1; i <= m; i++) {
			System.out.print(i + "\t");
		}
		System.out.println();
		for (int i = 0; i < n; i++) {
			System.out.print((i + 1) + "\t");
			System.out.print(w[i] + "\t");
			System.out.print(v[i] + "\t");
			for (int j = 0; j < m; j++) {
				System.out.print(t[i][j] + "\t");
			}
			System.out.println();
		}
		System.out.println();
	}

}

测试结果

两个测试结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
8
4
2 3 4 5
3 4 5 6
序号	重量	价值	1	2	3	4	5	6	7	8	
1	2	3	0	3	4	5	7	8	9	10	
2	3	4	0	0	4	5	6	6	9	10	
3	4	5	0	0	0	5	6	6	6	6	
4	5	6	0	0	0	0	6	6	6	6	

the bag max value: 10
the bag now weight: 8
the detail: [2, 4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
10
5
2 2 6 5 4
6 3 5 4 6
序号	重量	价值	1	2	3	4	5	6	7	8	9	10	
1	2	6	0	6	6	9	9	12	12	15	15	15	
2	2	3	0	3	3	6	6	9	9	9	10	11	
3	6	5	0	0	0	6	6	6	6	6	10	11	
4	5	4	0	0	0	6	6	6	6	6	10	10	
5	4	6	0	0	0	6	6	6	6	6	6	6	

the bag max value: 15
the bag now weight: 8
the detail: [1, 2, 5]

补充说明

可以使用一维数组来代替二维数组，在空间上能得到压缩，但是相应的如果需要输出最大价值时的具体放法就没法做到了。
二维数组可以输出具体的组合。

_常见的经典算法概念（摘自软考书）：

递归法：
递归法是指一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法。在使用递归策略时，必须有一个明确的递归结束条件（边界），称为递归出口。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。

递归次数过多容易造成栈溢出。

场合1: 数据的定义是按递归定义的(Fibonacci 函数)。
场合2: 问题解法按递归算法实现(回溯)。
场合3: 数据的结构形式是按递归定义的(树的遍历，图的搜索)。

两个步骤：分析递归关系，得出递推式；再确定最终终止条件，防止出现无限栈调用。

分治法：
对于一个规模为n的问题，若该问题可以容易地解决(如说规模n较小)则可以直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

问题规模缩小到一定的程度就可以容易地解决，可以分解为若干个规模较小的相同问题，利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的。

三个步骤：分解问题成小问题；找出小问题的解决方法；每次小问题解决后，逐渐合并，再利用相同的解决方法解决，最终解决原问题。

动态规划法：
这种算法也用到了分治思想，它的做法是将问题实例分解为更小、相似的子问题，并存储子问题的解而避免计算重复的子问题。

动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。

两个步骤：将问题划分成几种情况（阶段），找出每个情况下的状态方程；循环或递归的利用方程解决问题。

贪心算法：
它是一种不追求最优解，只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解而穷尽所有可能所必须耗费的大量时间。贪心算法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。

这类问题一般具有两个重要的性质：贪心选择性质，最优子结构性质。

贪心法经典应用有背包问题、活动安排问题等。

一般采用自顶而下的方法，分阶段进行，每个阶段选择最好的方案，采用“有好处就占着”的贪心策略。

三个步骤：从问题的某一个满足条件的初始解出发；循环求解，每次求出可行解的其中一个最好解；将所有的解组合成问题的一个解。

回溯算法(试探法)：
它是一种系统地搜索问题的解的方法。回溯算法的基本思想是: 从一条路往前走，能进则进，不能进则退回来，换一条路再试。其实现一般要用到递归和堆栈。

回溯是递归的一个特例，但它又有别于一般的递归法，用回翻法解题的一个显著特征是在搜索过程中动态产生问题的解空间。
在任何时刻，算法只保存从根结点到当前扩展结点的路径。

经典应用有迷官搜索、N皇后问题，骑土巡游、正则表达式匹配等。

回溯一般伴随着约束条件。

三个步骤：定义问题的解空间；确定易于搜索的解空间结构；以深度优先的方式搜索解空间，并注意剪枝。

以上算法中的分治法和动态规划法通常要用到回溯算法，而回溯算法又一般要用到递归，只有贪心算法与递归联系最弱。