文章目录

  之前的一次课老师给动态规划开了个头,虽然听得云里雾里的,不过感觉动态规划的解决问题思路很像我以前学的运筹学的解决问题的思维方式。

  尤其是做到LCS问题的时候画的那个矩阵,极其像我以前求输水管最佳排布之类问题时画的那种矩阵。

  动态规划具有的两个特性与运筹学中的最优化问题涉及到的特性高度一致:子问题的高度重复性、最优子结构性质,此外问题的最优解中包含着其每一个子问题的最优解也是一样的。

  课后又自己琢磨的半天,对动态规划的核心思路有了一点浅显的认识。课上留下了两个问题,第一个是矩阵连乘问题,第二个是LCS问题。下面一一给出大概的描述和解决思路以及java实现的解题代码。

  矩阵连乘问题:

  问题描述

  * 矩阵连乘问题(矩阵链乘法)

  一般描述:

  对于给定的n个矩阵,M 1 , M 2 ,…, M n ,其中矩阵M i 和M j 是可乘的,要求确定计算矩阵连乘积( M 1 M 2 …M n )的计算次序,使得按照该次数计算矩阵连乘积时需要的乘法次数最少

  例 ,设有矩阵M 1 ,M 2 ,M 3 ,M 4

  其维数分别是:10×20, 20×50,50×1 ,1×100

  现要求出这4个矩阵相乘的结果

  计算次序可以通过加括号的方式确定

  代码:

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
/**
* 矩阵连乘问题的动态规划方法求解
* @author jrhu05
*
*/
public class MatrixMultiplication {
public static void main(String[] args) {
int[] p={10,20,50,1,100};//表示10*20的矩阵再乘上20*50再乘上XXX类推
double times=multiplication(p,3);
System.out.println(times);
}
/**
* 计算最小的乘法次数
* @param p
* @param end 需要计算到的位置
* @return
*/
private static double multiplication(int[] p,int end) {
// TODO 自动生成的方法存根
double[][] m = new double[end+1][end+1];
for (int i = 0; i <=end; i++) {
m[i][i]=0;
}
for (int l = 1; l < end; l++) {
for (int i = 1; i <= end-l; i++) {
int j=i+l;
double min;
//矩阵M t 的列数为r t
min=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];
for(int k=i;k<j;k++){
double temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if (temp<min) {
min=temp;
}
}
m[i][j]=min;
}

}
return m[1][end];
}
}

  最长公共子序列问题(LCS问题):

  问题的描述和求解思路网上有很多现成的资料,不在赘述直接贴实现的代码。

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
package dynamicProgramming;

import java.util.Arrays;

/**
* 动态规划法求解最长公共子序列问题
* @author jrhu05
*
*/
public class LCS {
static int count=0;
static int max_lcs_length=0;
static String[] result;
public static void main(String[] args) {
String[] s1={"A","B","C","B","D","A","B"};
String[] s2={"B","D","C","A","B","A"};
System.out.println("s1: "+Arrays.toString(s1));
System.out.println("s2: "+Arrays.toString(s2));
int row=s1.length+1;
int col=s2.length+1;
lcs(s1,s2, row, col);
}

private static void lcs(String[] s1, String[] s2,int row,int col) {
// TODO 自动生成的方法存根
int[][] matrix=new int[row][col];
String[][] operation=new String[row][col];
for(int i=0;i<col;i++){
matrix[0][i]=0;
}
for(int j=0;j<row;j++){
matrix[j][0]=0;
}
for(int i=1;i<row;i++){
for(int j=1;j<col;j++){
if (s1[i-1]==s2[j-1]) {
matrix[i][j]=matrix[i-1][j-1]+1;
operation[i][j]="upleft";
}else if (matrix[i-1][j]>matrix[i][j-1]) {
matrix[i][j]=matrix[i-1][j];
operation[i][j]="up";
}else if(matrix[i-1][j]<matrix[i][j-1]){
matrix[i][j]=matrix[i][j-1];
operation[i][j]="left";
}else {
matrix[i][j]=matrix[i-1][j];
operation[i][j]="upOrLeft";
}
}
}
//打印操作矩阵
// for (int i = 0; i < operation.length; i++) {
// String[] strings = operation[i];
// System.out.println(Arrays.toString(strings));
// }
System.out.println("the lcs's length is: "+matrix[row-1][col-1]);
max_lcs_length=matrix[row-1][col-1];
result=new String[max_lcs_length];
System.out.println("lcs is: ");
lcs_outPut(operation,s1,row-1,col-1,max_lcs_length);
//打印计算矩阵
// for (int i = 0; i < matrix.length; i++) {
// int[] js = matrix[i];
// for (int j = 0; j < js.length; j++) {
// int s = js[j];
// System.out.print(s+" ");
// }
// System.out.println();
// }
}

private static void lcs_outPut(String[][] operation, String[] s1, int row,
int col,int current_len) {
if (row==0||col==0) {
for(int s=0; s < max_lcs_length; s++)
{
System.out.print(result[s]);
}
System.out.println();
count++;
return;
}
if (operation[row][col].equals("upleft")) {
current_len--;
result[current_len]=s1[row-1];
lcs_outPut(operation, s1, row-1, col-1,current_len);

}else if (operation[row][col].equals("up")) {
lcs_outPut(operation, s1, row-1, col,current_len);
}else if (operation[row][col].equals("left")) {
lcs_outPut(operation, s1, row, col-1,current_len);
}else {
//等于的时候搜索上和左两侧的可能的操作集合
lcs_outPut(operation, s1, row-1, col,current_len);
lcs_outPut(operation, s1, row, col-1,current_len);
}
}

}

  LCS问题测试数据的运行结果如下:

  上周老师又给我们另外讲了几个动态规划的典型实例,最大子段和与01背包问题的动态规划解法。

  最大子段和的解法如下:

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
package dynamicProgramming;
/**
* 最大子段和问题的动态规划方法求解
* @author jrhu05
*
*/
public class MaxSubSum {
public static void main(String[] args) {
int[] a={-2,11,-4,13,-5,-2};
maxSum(a);
}
public static void maxSum(int[] a) {
int n=a.length;
int sum=0,b=0;//初始化最大子段和为0,b[0]为0
int start=0,end=0;
for (int i=0;i<n;i++) {
if (b>0) {
b+=a[i];
}else {
b=a[i];
start=i;
}
if (b>sum) {
sum=b;//更新找到的最大子段
end=i;
}
}
System.out.println("max subline sum is: "+sum);
System.out.println("from "+(start+1)+" to "+(end+1));
}
}

01背包问题的例题与实现如下:

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
package dynamicProgramming;

import java.util.Arrays;

/**
* 01背包问题的动态规划方法求解
* @author jrhu05
*
*/
public class ZeroOneBag {
/**
* 例题
* 假设现有容量10kg的背包,另外有3个物品,分别为a1,a2,a3。物品a1重量为3kg,
* 价值为4;物品a2重量为4kg,价值为5;物品a3重量为5kg,价值为6。
* 将哪些物品放入背包可使得背包中的总价值最大?
*/
public static void main(String[] args) {
int[] w={3,4,5};//各个物品的重量
int[] v={4,5,6};//各个物品对应的价值
int capacity=10;//背包容量
int maxValue= knap(w,v,capacity);
System.out.println("the max value: "+maxValue);
}

public static int knap(int[] w,int[] v,int capacity) {
int num=w.length;
//将重量数组处理为[0,3,4...]方便后续处理
int[] weight=new int[num+1];
weight[0]=0;
for (int i = 0; i < w.length; i++) {
weight[i+1]=w[i];
}
//同样处理价值数组
int value[]=new int[num+1];
value[0]=1;
for (int i = 0; i < v.length; i++) {
value[i+1] = v[i];

}
//建立用于求解需要的矩阵
int[][] c=new int[num+1][capacity+1];
//初始化
for (int i = 0; i < num+1; i++) {
c[i][0]=0;
}
for (int j = 0; j < capacity+1; j++) {
c[0][j]=0;
}
//构建该矩阵
for (int i = 1; i < num+1; i++) {
for (int j = 1; j < capacity+1; j++) {
c[i][j]=c[i-1][j];
if (weight[i]<=j) {
c[i][j]=Math.max(c[i][j],(c[i-1][j-weight[i]]+value[i]));
}
}
}
for (int i = 0; i < c.length; i++) {
int[] js = c[i];
System.out.println(Arrays.toString(js));
}
return c[num][capacity];
}
}

如果觉得文章很有趣或对你带来了帮助,欢迎请我喝杯咖啡哦~

文章目录