动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解 的处理算法 。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子 阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 ) 。
动态规划可以通过填表的方式来逐步推进，得到最优解。
动态规划算法最佳实践-背包问题
背包问题：有一个背包，容量为 4 磅 ， 现有如下物品：
| 物品 |
重量 |
价格 |
| 吉他（G） |
1 |
1500 |
| 音响（S） |
4 |
3000 |
| 电脑（L） |
3 |
2000 |
（1）要求达到的目标为装入的背包的总价值最大，并且重量不超出
（2）要求装入的物品不能重复
总体思路
根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。
动态规划的原理
动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。
最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。
背包问题的解决过程
每次遍历到的第 i 个物品，根据 w[i]和 v[i]来确定是否需要将该物品 放入背包中。即对于给定的 n 个物品，设 v[i]、w[i]分别为第 i 个物品的价值和重量，C 为背包的容量。再令 v[i][j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值。则我们有下面的结果：
1
2
3
4
5
6
7
8
9
| (1) v[i][0]=v[0][j]=0;
(2) 当 w[i]> j 时：v[i][j]=v[i-1][j]
单元格的装入策略
(3) 当 j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
v[i-1][j]： 就是上一个单元格的装入的最大值
v[i] : 表示当前商品的价值
v[i-1][j-w[i]] ： 装入 i-1 商品，到剩余空间 j-w[i]的最大值
|
这样我们就完成了填表找到了商品的最优解，但是最优解由哪些商品构成，我们却不知道，所以我们还有定义一个 item 一维数组，根据回溯法求解出最优解商品构成，在 item 上将其下标标记为1。有如下寻解方式：
- V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，则回到V(i-1,j)；
- V(i,j)=V(i-1,j-w(i))+v(i)时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到V(i-1,j-w(i))；
- 一直遍历到i＝0结束为止，所有解的组成都会找到。
以上所有代码如下：
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
|
public class KnapsackProblem {
public static final String things[] = {"", "吉他（G）","音响（S）","电脑（L）"};
public static final int weight[] = {0,1, 4, 3};
public static final int price[] = {0,1500, 3000, 2000};
static int row = things.length;
static int column = 4 + 1;
static int[][] V = new int[row][column];
static int[] w = weight;
static int[] v = price;
static int[] item = new int[row];
public static void main(String[] args) {
findMax();
list();
findWhat(row-1,column-1);
printWhat();
}
public static void findMax(){
for (int i = 1; i < row; i++) {
for (int j = 1; j < column; j++) {
if(w[i]>j){
V[i][j] = V[i-1][j];
}else {
V[i][j] = Math.max(V[i-1][j],v[i]+V[i-1][j-w[i]]);
}
}
}
}
public static void list(){
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
System.out.printf("%d\t",V[i][j]);
}
System.out.println();
}
}
public static void findWhat(int i, int j){
if(i==0)
return;
if(V[i][j] == V[i-1][j]){
findWhat(i-1,j);
}else if(j-w[i]>=0 && V[i][j] == v[i]+V[i-1][j-w[i]]){
item[i] = 1;
findWhat(i-1,j-w[i]);
}
}
public static void printWhat(){
System.out.print("最优解的商品构成：");
for (int i = 1, len = item.length; i < len; i++) {
if(item[i] == 1){
System.out.print(things[i]+" ");
}
}
System.out.println();
}
}
|
运行结果：
