动态规划法
最长公共子序列
题目：
求两个字符串 X 和 Y 的最长公共子序列长度。例如：”abcbdab” 和 “bdcaba” 的最长公共子序列之一为 “bcba”，故应输出 4。
思路：
利用动态规划法，在二维数组 c[m+1][n+1] 中保存 $X_i$ 与 $Y_j$ 的最长公共子序列（LCS）的长度，其中 m 和 n 分别代表 X 和 Y 的长度。求解 c 的规则如下：
- 如果 X[i] == Y[j]，那么 c[i][j] = c[i-1][j-1] + 1。试想：abcd 和 abcEd，因为 d == d，我们又知道 abc 和 abcE 的 LCS 长度为 3，所以这两个字符串的 LCS 长度应为 3+1=4。
- 如果不等，则 c[i][j] = MAX(c[i-1][j], c[i][j-1])。当前的字符不相等，故为上一次计算结果中较大的那个。
- i == 0 或 j == 0 时，为 0。
Java 实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int getLongestCommonSubsequenceLength(String X, String Y) {
int m = X.length();
int n = Y.length();
X = " " + X;
Y = " " + Y;
int c[][] = new int[m+1][n+1];
for(int i=1; i<=m; i++) {
c[i][0] = 0;
}
for(int i=1; i<=n; i++) {
c[0][i] = 0;
}
for(int i=1; i<=m; i++) {
for(int j=1; j<=n; j++) {
if(X.charAt(i) == Y.charAt(j)) {
c[i][j] = c[i-1][j-1] + 1;
} else {
c[i][j] = c[i-1][j] > c[i][j-1] ? c[i-1][j] : c[i][j-1];
}
}
}
return c[m][n];
}
|
为什么要在字符串前插入一个无意义的空格，并把数组长度设为 m+1，n+1 呢？因为 0 列和 0 行被我们全部置零用于满足第三条条件了，所以需要多一行、一列的存储空间。当然不存，手动判断也是可以的。
硬币问题
题目：
现有面值为 c1, c2, c3, … , cm 元的 m 种硬币，求支付 n 元时所需硬币的最少枚数。各面值的硬币可任意使用 n 次。
思路：
我们用 C[i] 表示第 i 种硬币的面值。用 T[i][j] 表示使用第 0 至第 i 种硬币支付 j 元时的最少硬币数。
那么，给定某个需要支付的金额 j，求解 T[i][j] 时有两个选择，一时选用第 i 种硬币，二是不用第 i 种硬币，我们选这两者之间较小的方案即可。也就是 T[i][j] = min(T[i-1][j], T[i][j-C[i]] + 1) 。
其中，T[i-1][j] 表示不使用，而 T[i][j-C[i]] 表示使用，所以还要多加上使用的这枚硬币。
但是我们没必要给每种面值都记录一个最优枚数，只需要记录最小的就可以了。因此可化简为 T[j] = min(T[j], T[j-C[i]]+1) 。
Java 实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| static int getMinNumOfCoin(int[] C, int amout) {
int[] T = new int[amout+1];
for(int i=0; i<T.length; i++) {
T[i] = Integer.MAX_VALUE;
}
T[0] = 0;
for(int i=0; i<C.length; i++) {
for(int j=C[i]; j<=amout; j++) {
T[j] = Integer.min(T[j], T[j-C[i]]+1);
}
}
return T[amout];
}
|
背包问题
题目：
现有价值分别为 $v_i$, 重量分别为 $w_i$ 的 N 块宝石。作为珠宝大盗的你，最多能背动总重量为 W 的背包。请问你这次盗窃的总收益最多为多少？
思路：
这道问题是每个物品选或不选的组合，因此被称为 0-1 背包问题。我们用 C[i][w] 表示前 i 个物品装入容量为 w 的背包时的总价值的最大值，递增背包容量 w 至最大值来求解。求出 C[i][w] 的值为以下二者中较大的一个：
C[i-1][w - 物品i的重量] + 物品i的价值C[i-1][w]
第一种即选择 i 的情况，第二种为不选择 i 的情况。
Java 实现：
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
| public class Main {
public static void main(String[] args) throws Exception {
Item[] items = new Item[5];
items[1] = new Item(4,2);
items[2] = new Item(5,2);
items[3] = new Item(2,1);
items[4] = new Item(8,3);
System.out.println(getMaxValue(items, 5));
}
static int getMaxValue(Item[] items, int weight) {
int[][] C = new int[items.length][weight+1];
for(int i=0; i<C.length; i++) {
for(int j=0; j<C[i].length; j++) {
C[i][j] = 0;
}
}
for(int i=1; i<items.length; i++) {
for(int j=1; j<=weight; j++) {
if(items[i].weight > j) {
} else {
C[i][j] = Integer.max(C[i-1][j], C[i-1][j-items[i].weight] + items[i].value);
}
}
}
return C[items.length-1][weight];
}
}
class Item {
public int value;
public int weight;
public Item(int value, int weight) {
this.value = value;
this.weight = weight;
}
}
|