什么是动态规划（DP）？
DP起源于运筹学，是求解决策过程最优化的数学方法，它一种是将多阶段过程转化为一系列单阶段问题，再利用各阶段之间的关系，逐个求解的方法。即动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。
动态规划干什么用？
求解决策过程最优化。因此动态规划算法通常用于求解具有某种最优性质的问题。
通常可按以下4个步骤设计：
找出最优解的性质，并刻画其结构特征。
递归地定义最优值。
以自底向上的方式计算出最优解。
根据计算最优值时得到的信息，构造最优解。
动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
如：
线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶 等；
经典例题01背包问题
问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
如：有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
本题特点是：每种物品仅有一件，可以选择放或不放。
F[i，j]表示在前i个物品中能够装入容量为j的背包中的最大价值。同时设v[i]、w[i]分别为第i个物品的价值和重量，v为背包的容量。
其状态转移方程便是：
F[i, v] = maxf{F[i-1, v], F[i-1, v-Ci] + Wi}
二维0-1背包问题
给定n种物品和一个背包。物品i的重量是wi，体积是bi，其价值为vi，背包的容量为c，容积为d。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品只有两个选择：装入或不装入，且不能重复装入。
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
| public class twobage {
public static int maxx(int a, int b) {
if (a >= b)
return a;
else
return b;
}
public static void main(String[] args) {
int[] weight = {5,3,8 };
int[] val = { 7,8,9 };
int[] b = { 4,6,2 };
int z = 30;
int p, q, i, m = 10;
int n = val.length;
int[][][] f = new int[n + 1][m + 1][z + 1];
int[] path = new int[n + 1];
for (i = 0; i <= n; i++)
f[i][0][0] = 0;
for (p = 0; p <= m; p++)
for (q = 0; q <= z; q++)
f[0][p][q] = 0;
for (i = 1; i <= n; i++)
for (p = 1; p <= m; p++)
for (q = 1; q <= z; q++) {
if (p < weight[i - 1] || q < b[i - 1]) {
f[i][p][q] = f[i - 1][p][q];
}else {
f[i][p][q] = maxx(f[i - 1][p][q], f[i - 1][p - weight[i - 1]][q - b[i - 1]] + val[i - 1]);
}
}
p = m;
q = z;
for (i = n; i >= 1; i--) {
if (f[i][p][q] > f[i - 1][p][q]) {
path[i] = 1;
p = p - weight[i-1];
q = q - b[i-1];
} else
path[i] = 0;
}
System.out.print("path值：");
for (i = 1; i <= n; i++)
System.out.print(path[i] + " ");
System.out.println();
System.out.print("放入的物品为：");
for (i = 1; i <= n; i++)
if(path[i]==1)
System.out.print(i-1+"号 ");
System.out.println();
int r = 0;
for (i = 1; i <= n; i++) {
if (path[i] == 1)
r += val[i - 1];
else
r += 0;
}
System.out.print("最大价值为："+r);
}
}
|
更多背包问题可以参考背包九讲
动态规划算法的基本要素
1. 最优子结构
2. 重叠子问题
3. 边界
4. 子问题独立
5. 备忘录方法
这里举个简单的例题：动态规划入门-数字三角形
Description
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的数字三角形中寻找一条从顶部到底边的路径，使得
路径上所经过的数字之和最大。路径上的每一步都只能往左下或
右下走。只需要求出这个最大和即可，不必给出具体路径。
三角形的行数大于1小于等于100，数字为 0 - 99
输入格式：
5 //三角形行数。下面是三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
要求输出最大和
Sample Output
30
代码：
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
| import java.util.Scanner;
public class triangle {
private static int max(int a, int b) {
if(a>b)
return a;
else return b;
}
public static void main(String[] args) {
System.out.print("请输入行数：");
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[][] a=new int[n+2][n+2];
int[][] path=new int[n+2][n+2];
int pmax=0;
for(int i=0;i<n+2;i++) {
a[i][i]=0;
}
for(int i=2;i<n+2;i++) {
for(int j=1;j<i;j++) {
a[i][j]=(int)sc.nextInt();
}
}
for(int i=2;i<n+2;i++) {
for(int j=1;j< i;j++) {
path[i][j]=max(path[i-1][j],path[i-1][j-1])+a[i][j];
}
}
for(int i=2;i<n+2;i++) {
for(int j=1;j< i;j++) {
System.out.print(path[i][j]+" ");
if (pmax < path[i][j]) {
pmax = path[i][j];
}
}
System.out.println();
}
System.out.println("最大值为："+pmax);
}
}
|
更多感悟，如果还有下次，再见~
