ARTS-第17周

发表于

ARTS （第17周）

开篇词

本周学习了动态规划的内容，发现一句话用来形容动态规划很好

千里之行，始于足下。

本周：

动态规划

Algorithm 算法

动态规划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
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
package dynamic_programming;

import java.util.Arrays;

public class DpTest01Package {
	public static void main(String[] args) {
		 test01Package();
		//t();
	}

	public static void t() {
		int[] arr = { 3, 2, 1 };
		int max = 10;
		int r = pack01_dp_better(arr, 0, 0, max);
		System.out.println("r:" + r);
	}

	static boolean[][] mem_p;
	static int t5 = 0;
	static int t4 = 0;
	static int t3 = 0;
	static int t2 = 0;
	static int t1 = 0;
	static int maxPackage = 0;
	static int maxPackage2 = 0;
	static int maxPackage3 = 0;//
	static int maxPackage4 = 0;//
	static int maxPackage5 = 0;//
	// 0-1背包

	public static void test01Package() {
		int times = 55555;
		int err = 0;
		int[] a = new int[13];
		// 8 9 6 :17
		for (int j = 0; j < times; j++) {

			maxPackage = 0;
			maxPackage2 = 0;
			maxPackage3 = 0;
			maxPackage4 = 0;//
			maxPackage5 = 0;//
			for (int i = 0; i < a.length; i++) {
				// 几种算法会因为a数组和max之间的关系不一样 而结果不一样

				// 如max是200， 数组都是0~5的值，那么maxPackage比maxPackage2慢
				// 如max是200， 数组都是0~200的值，那么maxPackage比maxPackage2快

				// maxPackage：在数组里的值对比max变量很大的时候会很快，如果数组里的值都很小就会很慢
				// maxPackage2：时间稳定
				// maxPackage3：很快，很快 但空间占用比别的大
				// maxPackage4：很快，空间占用大
				// maxPackage5：很快，空间占用相对不怎么大
				a[i] = (int) (Math.random() * 53) + 1;
			}
			int max = (int) (Math.random() * 1000 + 100);
			max = 10;
			System.out.println("===============");
			System.out.println("current:" + j);
			System.out.println(max + ":" + Arrays.toString(a));
			mem_p = new boolean[a.length + 1][max + 1];
			pack01_mem(a, 0, 0, max);
			fillPackage(max, 0, a, 0);
			fillPackage2(max, 0, a, 0);
			maxPackage4 = pack01_dp(a, 0, 0, max);
			maxPackage5 = pack01_dp_better(a, 0, 0, max);
			System.out.println("maxp5:" + maxPackage5);
			System.out.println("maxp4:" + maxPackage4);
			System.out.println("maxp3:" + maxPackage3);
			System.out.println("maxp2:" + maxPackage2);
			System.out.println("maxP1:" + maxPackage);
			if (maxPackage3 != maxPackage || maxPackage3 != maxPackage5 || maxPackage3 != maxPackage2
					|| maxPackage3 != maxPackage4) {
				err++;
				System.exit(0);
			}
		}
		//
		System.out.println("err:" + err);
		System.out.println("method1:" + t1);
		System.out.println("method2:" + t2);
		System.out.println("method3:" + t3);
		// System.out.println("method4:" + t4+"");
	}

	public static void fillPackage2(int m, int c, int[] it, int i) {
		t2++;
		int len = it.length;
		if (c == m || i >= len) {
			if (c > maxPackage2)
				maxPackage2 = c;
			return;
		}
		for (int j = i; j < it.length; j++) {
			if (it[j] + c <= m) {
				// 当作当前物品已经放入，然后进入下一个物品
				fillPackage2(m, c + it[j], it, j + 1);
			} else {
				// 不能放入就不累加重量，然后进入下一个物品
				fillPackage2(m, c, it, j + 1);
			}
		}

	}

	public static void fillPackage(int m, int c, int[] it, int i) {
		t1++;
		int len = it.length;
		if (c == m || i == len) {
			if (c > maxPackage)
				maxPackage = c;
			return;
		}
		// 把下一个物品当前当前填充的物品填充进去
		// 即
		// 第一次运行的时候 把第1个物品当作首个物品放进去
		// 第二次运行的时候 把第2个物品当作首个物品放进去
		fillPackage(m, c, it, i + 1);
		// 判断当前物品是否能放 能防就放
		// 不能放结束 即此路已经走到终点
		if (it[i] + c <= m) {
			// 当作当前物品已经放入，然后放入下一个物品
			fillPackage(m, c + it[i], it, i + 1);
		}
	}

	// 备忘录模式
	public static void pack01_mem(int[] it, int i, int c, int w) {
		if (mem_p[i][c])
			return;
		t3++;
		if (i == it.length || c == w) {
			if (c > maxPackage3) {
				maxPackage3 = c;
			}
			return;
		}

		// 能放
		for (int idx = i; idx < it.length; idx++) {
			mem_p[idx][c] = true;
			// 能放
			if (it[idx] + c <= w) {
				pack01_mem(it, idx + 1, c + it[idx], w);
			} else {
				// 不能放
				pack01_mem(it, idx + 1, c, w);
			}
		}
	}

	// 动态规划 优化版
	public static int pack01_dp_better(int[] it, int i, int c, int w) {
		boolean[] arr = new boolean[w + 1];
		arr[0] = true;
		if (it[0] <= w) {
			arr[it[0]] = true;
		}
		for (int j = 1; j < it.length; j++) {

			for (int x = w - it[j]; x >= 0; x--) {
				if (arr[x]) {
					arr[x + it[j]] = true;
				}
			}
		}
		for (int j = w; j > 0; j--) {
			if (arr[j] == true)
				return j;
		}
		return 0;
	}
	// 动态规划
	public static int pack01_dp(int[] it, int i, int c, int w) {
		boolean[][] arr = new boolean[it.length][w + 1];
		// 不放入的情况
		arr[0][0] = true;// 也是最基础的默认值，用于给后续构建
		if (it[0] <= w) {
			// 第一个物品重量 是可以达到的
			arr[0][it[0]] = true;
		}
		for (int j = 1; j < it.length; j++) {
			// 放入的情况
			// 当成 本次什么都不放入
			// 即备份一份上一行数组
			for (int x = 0; x <= w; x++) {
				arr[j][x] = arr[j - 1][x];

			}
			// 放入的情况
			// 重量允许
			for (int x = 0; x + it[j] <= w; x++) {
				// 去前一次结果里获取
				if (arr[j - 1][x]) {

					arr[j][x + it[j]] = true;
				}

			}
		}

		for (int j = w; j >= 0; j--) {
			if (arr[it.length - 1][j] == true) {

				return j;
			}
		}
		return 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
public static void getMoney(int[] it, int p, int max) {
		int p2 = p * max;
		int len = it.length;
		boolean[][] t = new boolean[len][p2];
		t[0][0] = true;
		if (it[0] <= p2) {
			t[0][it[0]] = true;
		}
		for (int i = 1; i < len; i++) {
			for (int j = 0; j < p2; j++) {
				t[i][j] = t[i - 1][j];
			}

			for (int j = 0; j + it[i] < p2; j++) {
				if (t[i - 1][j]) {
					t[i][j + it[i]] = true;
				}
			}

		}
		int r = -1;
		for (int i = p; i < p2; i++) {
			if (t[t.length - 1][i] == true) {
				r = i;
				break;
			}

		}
		if (r == -1) {
			System.out.println("没有");
			return;
		}
		System.out.println("有：" + r);
		// 从最后一个物品往前
		for (int i = it.length - 1; i >= 1; i--) {
			// 减去当前价钱 去前一行找
			// 有就是有放入
			if (r - it[i] >= 0 && t[i - 1][r - it[i]] == true) {
				System.out.println("第" + i + "个物品,价钱" + it[i]);
				r = r - it[i];
			}
			// 如果t[i - 1][r]==true可以理解成是当前物品不放入 这里就不继续写了
		}
		// 最后一个物品的判断 it[0][0]=true
		if (r != 0) {
			System.out.println("第" + 0 + "个物品,价钱" + it[0]);
		}
	}

Review 英文文章

http://dubbo.apache.org/en-us/docs/user/quick-start.html

dubbo 的介绍和简单开始。

Tip 技巧

极客时间的专栏《数据结构与算法之美》

本周学习了该专栏中的40-42篇

内容为动态规划：简而言之，动态规划就是构建出最基础的东西，然后根据底层的数据再逐层构建出更上层的东西。直到计算玩全部的数据。并且动态规划的效率较高。

Share 分享

https://blog.csdn.net/BEYONDMA/article/details/88365203

ai换脸原理