算法——贪心和动态规划

引言

本文整理了常见的动态规划和贪心的相关算法,方便以后查阅。算法相关的文章均收录于<算法系列文章>

动态规划

切割钢条问题

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
package bbm.dp;

/**
* Serling 公司购买长钢条, 将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。
* 假定我们知道 Seling 公司出售一段长度为 i 英寸的钢条的价格为P(i=1,2,⋯,单位为美元)。钢条的长度均为整英寸。下图图给出了一个价格表的样例。
* 长度i: 1 2 3 4 5 6 7 8 9 10
* 价格p: 1 5 8 9 10 17 17 20 24 30
*
* 本例采用动态规划方案,自底向下的求解各个子问题,并记录子问题的解,然后逐步的计算出原问题的解
*
* @author bbm
*/
public class CutRod {
int[] price = new int[] {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

public void cutRod(int n) {
int[] bestSum = new int[n + 1];
int[] bestCutSize = new int[n + 1];
bestSum[0] = 0;
for (int j = 1; j <= n; j++) {
int q = Integer.MIN_VALUE;
for (int i = 1; i <= j; i++) {
if (q < price[i] + bestSum[j - i]) {
q = price[i] + bestSum[j - i];
bestCutSize[j] = i;
}
}
bestSum[j] = q;
}
print(bestSum);
print(bestCutSize);
while (n > 0) {
System.out.println(bestCutSize[n]);
n = n-bestCutSize[n];
}
}

void print(int[] nums) {
for (int num : nums) {
System.out.print(num + " ");
}
System.out.println();
}

public static void main(String[] args) {
new CutRod().cutRod(7);
}
}

最大公共子序列

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
package bbm.dp;

import java.util.ArrayList;

/**
* 最大公共子序列:例如,ABCD 和 ACE 这两个序列的最大公共子序列为 AC
* 本例中采用动态规划的思想,从两个序列的头出发x[i], y[j],如果 x[i] y[j] 相等,那么到 x[i] y[j] 的最大公共子序列就比 x[i-1] y[j-1]
* 多 1,如果他们不相等,那么就要检查 x[i-1] y[j] 和 x[i] y[j-1] 为止哪边的子序列最大,让 x[i] y[j] 也等于该值,当 i j 达到 x y 的
* 末尾时,我们就得到了最大公共子序列
* @author bbm
*/
public class LongestCommonSubSequence {

public ArrayList<Character> lcsLength(char[] x, char[] y) {
char[][] path = new char[x.length + 1][y.length + 1];
int[][] length = new int[x.length + 1][y.length + 1];
for (int i = 0; i < x.length; i++) {
for (int j = 0; j < y.length; j++) {
if (x[i] == y[j]) {
length[i + 1][j + 1] = length[i][j] + 1;
path[i + 1][j + 1] = '↖';
} else if (length[i][j + 1] > length[i + 1][j]) {
length[i + 1][j + 1] = length[i][j + 1];
path[i + 1][j + 1] = '↑';
} else {
length[i + 1][j + 1] = length[i + 1][j];
path[i + 1][j + 1] = '←';
}
}
}
System.out.print(' ');
System.out.print(' ');
for (char c : y) {
System.out.print(c);
System.out.print(' ');
System.out.print(' ');
}
System.out.println();
for (int i = 1; i < path.length; i++) {
System.out.print(x[i - 1]);
System.out.print(' ');
for (int j = 1; j < path[i].length; j++) {
System.out.print(path[i][j]);
System.out.print(length[i][j]);
System.out.print(' ');
}
System.out.println();
}
ArrayList<Character> result = new ArrayList<>();
getPath(result, x, path, x.length, y.length);
return result;
}

private void getPath(ArrayList<Character> result, char[] x, char[][] path, int i, int j) {
if (i == 0 || j == 0) {
return;
}
if (path[i][j] == '↖') {
getPath(result, x, path, i - 1, j - 1);
result.add(x[i - 1]);
} else if (path[i][j] == '↑') {
getPath(result, x, path, i - 1, j);
} else {
getPath(result, x, path, i, j - 1);
}
}

public static void main(String[] args) {
ArrayList<Character> result = new LongestCommonSubSequence()
.lcsLength(new char[] {'a', 'b', 'c', 'b', 'd', 'a', 'b'}, new char[] {'b', 'd', 'c', 'a', 'b', 'a'});
System.out.print("LCS: ");
for (char c : result) {
System.out.print(c);
}
System.out.println();
}

}

最大子序列问题

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
package bbm.dp;

/**
* 这里我们用动态规划的思想重新解最大子序列的问题
*
* @author bbm
*/

public class DPMaxSubSequence {
public int maxSubArray(int[] nums) {
if (nums == null) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
// end 记录了以 i 为结尾的序列中最大的子序列和
int[] end = new int[nums.length];
end[0] = nums[0];
int max = end[0];
for(int i = 1; i < nums.length; i++) {
if (nums[i] > end[i - 1]) {
if (end[i-1] > 0) {
end[i] = end[i - 1] + nums[i];
} else {
end[i] = nums[i];
}
} else {
end[i] = end[i - 1] + nums[i];
}
if (end[i] > max) {
max = end[i];
}
}
return max;
}

public static void main(String[] args) {
DPMaxSubSequence maxSubSequence = new DPMaxSubSequence();
int result = maxSubSequence.maxSubArray(new int[] {-2, -1, 1 ,1, 4, -3, -4, 3});
System.out.println(result);
}
}

0-1 背包问题

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
package bbm.dp;

/**
* 0-1背包问题:给定一组多个物品,每种物品都有自己的重量和价值,在限定的总重量/总容量内,选择其中若干个(也即每种物品可以选0个或1个),
* 设计选择方案使得物品的总价值最高。
*
* 动态规划的思路是:逐渐的增加商品数量和背包容量
* 1. 如果新增的商品重量比当前背包容量大,把新增的商品排除掉,重新算总价值
* 2. 如果新增的商品重量比当前背包容量小,比较如下两种情况哪个总价值更高,选择总价高的那个方案:
* 2.1 新增的商品排除掉,重新算总价值
* 2.2 将新增商品放入包内,计算 (新商品 price + 剩余商品在剩下的容量下的最高价值)
* @author bbm
*/
public class KnapsackProblem {

public int findBestSolution(int[] price, int[] weight, int maxWeight) {
int itemCount = price.length;
int[][] memo = new int[itemCount + 1][maxWeight + 1];
int max = Integer.MIN_VALUE;
for (int i = 1; i <= itemCount; i++) {
for (int j = 1; j <= maxWeight; j++) {
if (weight[i - 1] > j) {
memo[i][j] = memo[i - 1][j];
} else {
memo[i][j] = Math.max(memo[i - 1][j], price[i - 1] + memo[i - 1][j - weight[i - 1]]);
}
}
if (memo[i][maxWeight] > max) {
max = memo[i][maxWeight];
}
}
System.out.print("\t");
for (int i = 0; i <= maxWeight; i++) {
System.out.print(i + "\t");
}
System.out.println();
for (int i = 0; i < memo.length; i++) {
System.out.print(i + "\t");
for (int j = 0; j < memo[i].length; j++) {
System.out.print(memo[i][j] + "\t");
}
System.out.println();
}
System.out.println();
return max;
}

public static void main(String[] args) {
int maxPrice = new KnapsackProblem().findBestSolution(new int[] {1, 6, 18, 22, 28},
new int[] {1, 2, 5, 6, 7}, 11);
System.out.println(maxPrice);
}
}

贪心算法

活动选择

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
package bbm.greedy;

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

/**
* 活动选择问题:已知一些活动的开始时间和结束时间,计算怎么安排活动能让尽可能多的活动互不重叠。
* activity 0 1 2 3 4 5 6 7 8 9 10
* start 1 3 0 5 3 5 6 8 8 2 12
* end 4 5 6 7 9 9 10 11 12 14 16
* 这里我们已经对 end time 进行了排序,而 end time 最小的值肯定会出现在最优解中,如果最优解的第一个活动 end time >= activity 0 的 end time
* 那么我们完全可以用 activity 0 来替换最优解的第一个活动,而如果最优解的第一个活动是 end time < activity 0 的 end time,这并不会发生,因为
* activity 0 的 end time 就是最小了。
*
* 基于上述规律,我们可以利用贪心算法,按照 end time 递增的顺序遍历所有 activity 如果 activity 的 start end 大于最优活动集的所有活动的 end time
* 那么我们就将这个新活动加入到 最优活动集,重复该过程知道遍历完所有活动,我们就得到了最终的最优活动集
* @author bbm
*/
public class ActivitySelector {
public List<Integer> activitySelector(int[] start, int[] end) {
List<Integer> result = new ArrayList<>();
result.add(0);
int lastEnd = end[0];
for (int i = 1; i < start.length; i++) {
if (start[i] > lastEnd) {
result.add(i);
lastEnd = end[i];
}
}
return result;
}

public static void main(String[] args) {
List<Integer> result = new ActivitySelector().activitySelector(new int[] {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12},
new int[] {4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16});
for (int i : result) {
System.out.print(i);
System.out.print(' ');
}
System.out.println();
}
}

哈夫曼编码

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
package bbm.greedy;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
* 哈夫曼编码根据字符出现的频率来规划每个字符使用什么编码,它将构建一个二叉树,出现频率越高的字符越接近树根,然后从根节点数出发,当经过左节点
* 时记录编码值0,当经过右节点时记录编码值1,按照这样的规则,从根节点到任意实际字符节点所记录的所有编码值,就是该字符的编码,例如
* &
* /\
* & c
* /\
* a b
* 上树中, a 的编码就是 00,b 的编码是 01,c 的编码是 1
*
* 那么怎么构建上面这棵编码树呢,我们可以采用贪心的思路,
* 1. 先对所有字符创建其对应的树节点,得到一个节点集合 nodes,
* 2. 然后根据所有字符出现的频率,每次拿出节点集合 nodes 中频率最低的两个节点,为它们创建一个父节点,并将父节点放入 nodes 中
* 3. 重复该过程直到 nodes 中只含有一个节点时,该节点就是树根 root 节点
* @author bbm
*/
public class Huffman {

public Node encode(char[] chars, int[] frequencies) {
List<Node> nodes = new ArrayList<>();
for (int i = 0; i < chars.length; i++) {
nodes.add(new Node(frequencies[i], chars[i]));
}
nodes.sort(Comparator.comparingInt(o -> o.freq));
while (nodes.size() > 1) {
Node left = nodes.remove(0);
Node right = nodes.remove(0);
Node newNode = new Node(left.freq + right.freq, '&');
newNode.left = left;
newNode.right = right;
nodes.add(newNode);
nodes.sort(Comparator.comparingInt(o -> o.freq));
}
return nodes.get(0);
}

public static void main(String[] args) {
Node result = new Huffman().encode(new char[] {'f', 'e', 'c', 'b', 'd', 'a'}, new int[] {5, 9, 12, 13, 16, 45});
result.print(0);
}

public static class Node {
int freq;
char ch;
Node left;
Node right;

public Node(int freq, char ch) {
this.freq = freq;
this.ch = ch;
}

public void print(int depth) {
for (int i = 0; i < depth; i++) {
System.out.print('-');
}
System.out.println(ch + ":" + freq);
if (left != null) {
left.print(depth + 1);
}
if (right != null) {
right.print(depth + 1);
}
}
}
}

参考内容

[1] 《算法导论》
[2] 0-1背包问题的动态规划算法

贝克街的流浪猫 wechat
您的打赏将鼓励我继续分享!
  • 本文作者: 贝克街的流浪猫
  • 本文链接: https://www.beikejiedeliulangmao.top/algorithm/dp-greedy/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议,转载请注明出处!
  • 创作声明: 本文基于上述所有参考内容进行创作,其中可能涉及复制、修改或者转换,图片均来自网络,如有侵权请联系我,我会第一时间进行删除。