Juliet
- 浏览: 108864 次
- 性别:
- 来自: 西安
-
文章分类
最新评论
-
zhng：
mark,今天电面问到这个问题，还没接触过，临时报佛脚。
AJAX 跨域访问 — 方法大全 -
jssay：
有时间一定要拜读一下，楼主辛苦了！
AJAX 跨域访问 — 方法大全 -
HK.Night：
1024～～～
AJAX 跨域访问 — 方法大全 -
zhaozk：
mark too
AJAX 跨域访问 — 方法大全 -
mrlee09：
mark mark mark
AJAX 跨域访问 — 方法大全
最简单地：v是空间，w是价值，要求总价值最大
dp[v] = max {dp[v-v[i]] + w[i]};//自顶向下；
//自底向上
1. /**********************************************************
2. * 0-1背包问题
3. *
4. * 问题描述：
5. * 给定n种物品和一背包。物品 i 的重量是 w[i] ，其价值为
6. * v[i] ，背包的容量为 c 。问:应该如何选择装入背包中的物品，
7. * 使得装入背包中物品的总价值最大？
8. *
9. * 在选择装入背包中的物品时，对每种物品 i 只有两种选择，
10. * 即装入或不装入背包。不能将物品 i 装入背包多次，也不能只
11. * 装入部分的物品 i 。因此，该问题称为 0-1 背包问题。
12. *
13. * 此问题的形式化描述为，给定 c > 0, w[i] > 0, v[i] > 0
14. * 1 <= i <= n ,要求找出 n 元 0-1 向量 x[1 .. n], 其中x[i]
15. * 等于0或1,使得对 w[i] * x[i] 求和小于等于 c ，并且 v[i] *
16. * x[i]达到最大。因此，0-1背包问题是一个特殊的整数规划问题。
17. *
18. ***********************************************************/
19.
20.
21. public class BagZeroOne {
22.
23. /**********************************************************************
24. * 动态规划解 (Dynamic Programming)
25. *
26. * @param v in the 物品价值数组
27. * @param w in the 物品重量数组
28. * @param c in the 背包的容量
29. * @param m out the 最优值数组，m[i][j]即背包容量为j,可选物品为 i, i + 1, ... , n 时0-1背包问题的最优值
30. *
31. * 由于0-1背包问题的最优子结构性质，可以建立计算m[i][j]的递归式如下：
32. * / max{m[i + 1][j]), m[i + 1][j - w[i]] + v[i]} j >= w[i]
33. * m[i][j] /
34. * \
35. * \ m[i + 1][j] 0 <= j < w[i]
36. *
37. * / v[n] j >= w[n]
38. * m[n][j] /
39. * \
40. * \ 0 0 <= j < w[n]
41. *
42. **********************************************************************/
43. public static void knapsack(int[] v, int[] w, int c, int[][] m) {
44. int n = v.length - 1;
45. int jMax = Math.min(w[n] - 1, c);
46. for (int j = 0; j <= jMax; j++) {
47. m[n][j] = 0;
48. }
49. for (int j = w[n]; j <= c; j++) {
50. m[n][j] = v[n];
51. }
52. for (int i = n - 1; i > 0; i--) {
53. jMax = Math.min(w[i] - 1, c);
54. for (int j = 0; j <= jMax; j++) {
55. m[i][j] = m[i + 1][j];
56. }
57. for (int j = w[i]; j <= c; j++) {
58. m[i][j] = Math.max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
59. }
60. }
61. /*
62. m[1][c] = m[2][c];
63. if (c >= w[1]) {
64. m[1][c] = Math.max(m[1][c], m[2][c - w[1]] + v[1]);
65. }
66. */
67. }
68.
69. /**
70. * @param m in the 最优值数组
71. * @param w in the 重量数组
72. * @param c in the 背包容量
73. * @param x out the 物品选择数组 if x[i] == 1 则选物品 i, 否则不选
74. **/
75. public static void trackback(int[][] m, int[] w, int c, int[] x) {
76. int n = w.length - 1;
77. for (int i = 1; i < n; i++) {
78. if (m[i][c] == m[i + 1][c]) {
79. x[i] = 0; //不选物品 i
80. } else {
81. x[i] = 1; //选择物品 i
82. c -= w[i]; //剩余容量
83. }
84. }
85. x[n] = (m[n][c] > 0)? 1: 0;
86. }
87.
88. public static void testDynamicProgramming() {
89. System.out.print("1. --- testDynamicProgramming ---> ");
90. //输入
91. int c = 7;
92. int[] w = {0, 5, 3, 2, 1};
93. int[] v = {0, 4, 4, 3, 1};
94.
95. //应该的输出
96. int expectedVMax = 8;
97. int[] expectedX = {0, 0, 1, 1, 1};
98.
99. //程序运行时变量
100. int[][] m = new int[w.length][c + 1];
101. int[] x = new int[w.length];
102.
103.
104. knapsack(v, w, c, m);
105. trackback(m, w, c, x);
106.
107. if (m[1][c] == expectedVMax && java.util.Arrays.equals(x, expectedX)) {
108. System.out.println("Test success!");
109. } else {
110. System.out.println("Test fail!");
111. }
112. }
113.
114. /******************************************************************************
115. * 暴力解 (Brutal Force)
116. *
117. * 物品 i 的重量 w[i], 价值 v[i]
118. *
119. * 递归算法
120. * try (物品 i, 当前选择已经达到的重量之和 tw, 本方案可能达到的总价值 tv)
121. * {
122. * //考虑物品 i 包含在当前方案的可能性
123. * if (包含物品 i 是可接受的)
124. * {
125. * 将物品 i 包含在当前方案中；
126. * if (i < n - 1)
127. * try(i + 1, tw + w[i], tv);
128. * else //又是一个完整方案，因它比前面的方案要好，以它作为最佳方案
129. * 以当前方案作为临时最佳方案保存
130. * 恢复物品 i 不包含在内的状态
131. * }
132. * //考虑物品 i 不包含在当前方案中的可能性
133. * if (不包含物品 i 仅是可考虑的)
134. * {
135. * if (i < n - 1)
136. * try(i + 1, tw, tv - v[i]);
137. * else //又是一个完整方案，因它比前面的方案要好，以它作为最佳方案
138. * 以当前方案作为临时最佳方案保存
139. * }
140. * }
141. ******************************************************************************/
142.
143. private static int[] w; //重量
144. private static int[] v; //价值
145. private static int[] x; //最优解
146. private static int[] opt; //有效解
147. private static int c; //背包容量
148. private static int maxv; //最优值
149.
150. public static void find(int i, int tw, int tv) {
151. //考虑物品 i 包含在当前方案中的可能性
152. if (tw + w[i] <= c) { //包含物品 i 是可以接受的
153. opt[i] = 1;
154. if (i < w.length - 1) {
155. find(i + 1, tw + w[i], tv);
156. } else { //又是一个完整方案，因它比前面的方案好，以它作为最佳方案
157. for (int j = 0; j < x.length; j++) {
158. x[j] = opt[j];
159. }
160. maxv = tv;
161. }
162. opt[i] = 0;
163. }
164. //考虑物品 i 不包含在当前方案中的可能性
165. if (tv - v[i] > maxv) { //不包含物品 i 是可以考虑的
166. if (i < w.length - 1) {
167. find(i + 1, tw, tv - v[i]);
168. } else { //又是一个完整方案，因它比前面的方案好，以它作为最佳方案
169. for (int j = 0; j < x.length; j++) {
170. x[j] = opt[j];
171. }
172. maxv = tv - v[i];
173. }
174. }
175. }
176.
177. public static void testBrutalForceRecursive() {
178. System.out.print("2. --- testBrutalForceRecursive ---> ");
179. int[] expectedX = {0, 1, 1, 1};
180. int expectedMaxV = 8;
181.
182. w = new int[] {5, 3, 2, 1};
183. v = new int[] {4, 4, 3, 1};
184. x = new int[w.length];
185. opt = new int[w.length];
186. c = 7;
187. int tv = 0;
188. for (int i : v) {
189. tv += i;
190. }
191.
192. find(0, 0, tv);
193. // System.out.println("maxv = " + maxv);
194. // System.out.println("x = " + java.util.Arrays.toString(x));
195. if (maxv == expectedMaxV && java.util.Arrays.equals(x, expectedX)) {
196. System.out.println("Test success!");
197. } else {
198. System.out.println("Test fail!");
199. }
200. }
201.
202. /****************************************************************
203. * 暴力解 (Brutal Force)
204. *
205. * 非递归算法
206. *
207. *
208. *****************************************************************/
209.
210. //当前候选解中各物品的考虑和选择状态，以及置该物品候选解的状态
211. private static int[] flag; //物品的考虑状态：0.不选;1.将被考虑;2.曾被选中
212. private static int[] twe; //已经达到的总重量
213. private static int[] tve; //期望的总价值
214.
215. private static int maxw; //背包容量
216. private static int[] cop; //临时最佳解的物品选择方案，当cop[i] 为 1 时，物品 i 在解中
217.
218. //将考虑物品 i
219. private static void next(int i, int tw, int tv) {
220. flag[i] = 1;
221. twe[i] = tw;
222. tve[i] = tv;
223. }
224. public static int find(int[] w, int[] v, int n) {
225. int i, k, f;
226. int maxv, tw, tv, totv = 0;
227. maxv = 0;
228. for (int value : v) {
229. totv += value;
230. }
231. next(0, 0, totv);
232. i = 0;
233.
234. while (i >= 0) {
235. f = flag[i];
236. tw = twe[i];
237. tv = tve[i];
238. switch (f) {
239. case 0: //回退
240. i--;
241. break;
242.
243. case 1: //考虑被选中
244. flag[i]++;
245. if (tw + w[i] <= maxw) { //选中可行吗？
246. if (i < n - 1) {
247. next(i + 1, tw + w[i], tv);
248. i++;
249. } else {
250. maxv = tv;
251. for (k = 0; k < n; k++) {
252. cop[k] = ((flag[k] != 0)? 1 : 0);
253. }
254. }
255. }
256. break;
257.
258. default: //flag等于2
259. flag[i] = 0;
260. if (tv - v[i] > maxv) { //不选物品 i 可行吗？
261. if (i < n - 1) {
262. next(i + 1, tw, tv - v[i]);
263. i++;
264. } else {
265. maxv = tv - v[i];
266. for (k = 0; k < n; k++) {
267. cop[k] = ((flag[k] != 0)? 1 : 0);
268. }
269. }
270. }
271. break;
272. }
273. }
274. return maxv;
275. }
276.
277. public static void testBrutalForceNotRecursive() {
278. System.out.print("3. --- testBrutalForceNotRecursive ---> ");
279. int[] expectedX = {0, 1, 1, 1};
280. int expectedMaxV = 8;
281.
282. int[] w = new int[] {5, 3, 2, 1};
283. int[] v = new int[] {4, 4, 3, 1};
284. int n = w.length;
285.
286. cop = new int[n];
287.
288. flag = new int[n];
289. twe = new int[n];
290. tve = new int[n];
291.
292. maxw = 7;
293.
294. int maxv = find(w, v, n);
295. // System.out.println("maxv = " + maxv);
296. // System.out.println("x = " + java.util.Arrays.toString(x));
297. if (maxv == expectedMaxV && java.util.Arrays.equals(cop, expectedX)) {
298. System.out.println("Test success!");
299. } else {
300. System.out.println("Test fail!");
301. }
302.
303. }
304.
305. public static void main(String[] args) {
306. testDynamicProgramming();
307. testBrutalForceRecursive();
308. testBrutalForceNotRecursive();
309. }
310. }
dp[v] = max {dp[v-v[i]] + w[i]};//自顶向下；
//自底向上
1. /**********************************************************
2. * 0-1背包问题
3. *
4. * 问题描述：
5. * 给定n种物品和一背包。物品 i 的重量是 w[i] ，其价值为
6. * v[i] ，背包的容量为 c 。问:应该如何选择装入背包中的物品，
7. * 使得装入背包中物品的总价值最大？
8. *
9. * 在选择装入背包中的物品时，对每种物品 i 只有两种选择，
10. * 即装入或不装入背包。不能将物品 i 装入背包多次，也不能只
11. * 装入部分的物品 i 。因此，该问题称为 0-1 背包问题。
12. *
13. * 此问题的形式化描述为，给定 c > 0, w[i] > 0, v[i] > 0
14. * 1 <= i <= n ,要求找出 n 元 0-1 向量 x[1 .. n], 其中x[i]
15. * 等于0或1,使得对 w[i] * x[i] 求和小于等于 c ，并且 v[i] *
16. * x[i]达到最大。因此，0-1背包问题是一个特殊的整数规划问题。
17. *
18. ***********************************************************/
19.
20.
21. public class BagZeroOne {
22.
23. /**********************************************************************
24. * 动态规划解 (Dynamic Programming)
25. *
26. * @param v in the 物品价值数组
27. * @param w in the 物品重量数组
28. * @param c in the 背包的容量
29. * @param m out the 最优值数组，m[i][j]即背包容量为j,可选物品为 i, i + 1, ... , n 时0-1背包问题的最优值
30. *
31. * 由于0-1背包问题的最优子结构性质，可以建立计算m[i][j]的递归式如下：
32. * / max{m[i + 1][j]), m[i + 1][j - w[i]] + v[i]} j >= w[i]
33. * m[i][j] /
34. * \
35. * \ m[i + 1][j] 0 <= j < w[i]
36. *
37. * / v[n] j >= w[n]
38. * m[n][j] /
39. * \
40. * \ 0 0 <= j < w[n]
41. *
42. **********************************************************************/
43. public static void knapsack(int[] v, int[] w, int c, int[][] m) {
44. int n = v.length - 1;
45. int jMax = Math.min(w[n] - 1, c);
46. for (int j = 0; j <= jMax; j++) {
47. m[n][j] = 0;
48. }
49. for (int j = w[n]; j <= c; j++) {
50. m[n][j] = v[n];
51. }
52. for (int i = n - 1; i > 0; i--) {
53. jMax = Math.min(w[i] - 1, c);
54. for (int j = 0; j <= jMax; j++) {
55. m[i][j] = m[i + 1][j];
56. }
57. for (int j = w[i]; j <= c; j++) {
58. m[i][j] = Math.max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
59. }
60. }
61. /*
62. m[1][c] = m[2][c];
63. if (c >= w[1]) {
64. m[1][c] = Math.max(m[1][c], m[2][c - w[1]] + v[1]);
65. }
66. */
67. }
68.
69. /**
70. * @param m in the 最优值数组
71. * @param w in the 重量数组
72. * @param c in the 背包容量
73. * @param x out the 物品选择数组 if x[i] == 1 则选物品 i, 否则不选
74. **/
75. public static void trackback(int[][] m, int[] w, int c, int[] x) {
76. int n = w.length - 1;
77. for (int i = 1; i < n; i++) {
78. if (m[i][c] == m[i + 1][c]) {
79. x[i] = 0; //不选物品 i
80. } else {
81. x[i] = 1; //选择物品 i
82. c -= w[i]; //剩余容量
83. }
84. }
85. x[n] = (m[n][c] > 0)? 1: 0;
86. }
87.
88. public static void testDynamicProgramming() {
89. System.out.print("1. --- testDynamicProgramming ---> ");
90. //输入
91. int c = 7;
92. int[] w = {0, 5, 3, 2, 1};
93. int[] v = {0, 4, 4, 3, 1};
94.
95. //应该的输出
96. int expectedVMax = 8;
97. int[] expectedX = {0, 0, 1, 1, 1};
98.
99. //程序运行时变量
100. int[][] m = new int[w.length][c + 1];
101. int[] x = new int[w.length];
102.
103.
104. knapsack(v, w, c, m);
105. trackback(m, w, c, x);
106.
107. if (m[1][c] == expectedVMax && java.util.Arrays.equals(x, expectedX)) {
108. System.out.println("Test success!");
109. } else {
110. System.out.println("Test fail!");
111. }
112. }
113.
114. /******************************************************************************
115. * 暴力解 (Brutal Force)
116. *
117. * 物品 i 的重量 w[i], 价值 v[i]
118. *
119. * 递归算法
120. * try (物品 i, 当前选择已经达到的重量之和 tw, 本方案可能达到的总价值 tv)
121. * {
122. * //考虑物品 i 包含在当前方案的可能性
123. * if (包含物品 i 是可接受的)
124. * {
125. * 将物品 i 包含在当前方案中；
126. * if (i < n - 1)
127. * try(i + 1, tw + w[i], tv);
128. * else //又是一个完整方案，因它比前面的方案要好，以它作为最佳方案
129. * 以当前方案作为临时最佳方案保存
130. * 恢复物品 i 不包含在内的状态
131. * }
132. * //考虑物品 i 不包含在当前方案中的可能性
133. * if (不包含物品 i 仅是可考虑的)
134. * {
135. * if (i < n - 1)
136. * try(i + 1, tw, tv - v[i]);
137. * else //又是一个完整方案，因它比前面的方案要好，以它作为最佳方案
138. * 以当前方案作为临时最佳方案保存
139. * }
140. * }
141. ******************************************************************************/
142.
143. private static int[] w; //重量
144. private static int[] v; //价值
145. private static int[] x; //最优解
146. private static int[] opt; //有效解
147. private static int c; //背包容量
148. private static int maxv; //最优值
149.
150. public static void find(int i, int tw, int tv) {
151. //考虑物品 i 包含在当前方案中的可能性
152. if (tw + w[i] <= c) { //包含物品 i 是可以接受的
153. opt[i] = 1;
154. if (i < w.length - 1) {
155. find(i + 1, tw + w[i], tv);
156. } else { //又是一个完整方案，因它比前面的方案好，以它作为最佳方案
157. for (int j = 0; j < x.length; j++) {
158. x[j] = opt[j];
159. }
160. maxv = tv;
161. }
162. opt[i] = 0;
163. }
164. //考虑物品 i 不包含在当前方案中的可能性
165. if (tv - v[i] > maxv) { //不包含物品 i 是可以考虑的
166. if (i < w.length - 1) {
167. find(i + 1, tw, tv - v[i]);
168. } else { //又是一个完整方案，因它比前面的方案好，以它作为最佳方案
169. for (int j = 0; j < x.length; j++) {
170. x[j] = opt[j];
171. }
172. maxv = tv - v[i];
173. }
174. }
175. }
176.
177. public static void testBrutalForceRecursive() {
178. System.out.print("2. --- testBrutalForceRecursive ---> ");
179. int[] expectedX = {0, 1, 1, 1};
180. int expectedMaxV = 8;
181.
182. w = new int[] {5, 3, 2, 1};
183. v = new int[] {4, 4, 3, 1};
184. x = new int[w.length];
185. opt = new int[w.length];
186. c = 7;
187. int tv = 0;
188. for (int i : v) {
189. tv += i;
190. }
191.
192. find(0, 0, tv);
193. // System.out.println("maxv = " + maxv);
194. // System.out.println("x = " + java.util.Arrays.toString(x));
195. if (maxv == expectedMaxV && java.util.Arrays.equals(x, expectedX)) {
196. System.out.println("Test success!");
197. } else {
198. System.out.println("Test fail!");
199. }
200. }
201.
202. /****************************************************************
203. * 暴力解 (Brutal Force)
204. *
205. * 非递归算法
206. *
207. *
208. *****************************************************************/
209.
210. //当前候选解中各物品的考虑和选择状态，以及置该物品候选解的状态
211. private static int[] flag; //物品的考虑状态：0.不选;1.将被考虑;2.曾被选中
212. private static int[] twe; //已经达到的总重量
213. private static int[] tve; //期望的总价值
214.
215. private static int maxw; //背包容量
216. private static int[] cop; //临时最佳解的物品选择方案，当cop[i] 为 1 时，物品 i 在解中
217.
218. //将考虑物品 i
219. private static void next(int i, int tw, int tv) {
220. flag[i] = 1;
221. twe[i] = tw;
222. tve[i] = tv;
223. }
224. public static int find(int[] w, int[] v, int n) {
225. int i, k, f;
226. int maxv, tw, tv, totv = 0;
227. maxv = 0;
228. for (int value : v) {
229. totv += value;
230. }
231. next(0, 0, totv);
232. i = 0;
233.
234. while (i >= 0) {
235. f = flag[i];
236. tw = twe[i];
237. tv = tve[i];
238. switch (f) {
239. case 0: //回退
240. i--;
241. break;
242.
243. case 1: //考虑被选中
244. flag[i]++;
245. if (tw + w[i] <= maxw) { //选中可行吗？
246. if (i < n - 1) {
247. next(i + 1, tw + w[i], tv);
248. i++;
249. } else {
250. maxv = tv;
251. for (k = 0; k < n; k++) {
252. cop[k] = ((flag[k] != 0)? 1 : 0);
253. }
254. }
255. }
256. break;
257.
258. default: //flag等于2
259. flag[i] = 0;
260. if (tv - v[i] > maxv) { //不选物品 i 可行吗？
261. if (i < n - 1) {
262. next(i + 1, tw, tv - v[i]);
263. i++;
264. } else {
265. maxv = tv - v[i];
266. for (k = 0; k < n; k++) {
267. cop[k] = ((flag[k] != 0)? 1 : 0);
268. }
269. }
270. }
271. break;
272. }
273. }
274. return maxv;
275. }
276.
277. public static void testBrutalForceNotRecursive() {
278. System.out.print("3. --- testBrutalForceNotRecursive ---> ");
279. int[] expectedX = {0, 1, 1, 1};
280. int expectedMaxV = 8;
281.
282. int[] w = new int[] {5, 3, 2, 1};
283. int[] v = new int[] {4, 4, 3, 1};
284. int n = w.length;
285.
286. cop = new int[n];
287.
288. flag = new int[n];
289. twe = new int[n];
290. tve = new int[n];
291.
292. maxw = 7;
293.
294. int maxv = find(w, v, n);
295. // System.out.println("maxv = " + maxv);
296. // System.out.println("x = " + java.util.Arrays.toString(x));
297. if (maxv == expectedMaxV && java.util.Arrays.equals(cop, expectedX)) {
298. System.out.println("Test success!");
299. } else {
300. System.out.println("Test fail!");
301. }
302.
303. }
304.
305. public static void main(String[] args) {
306. testDynamicProgramming();
307. testBrutalForceRecursive();
308. testBrutalForceNotRecursive();
309. }
310. }
分享到：
发表评论
-
istringstream用法
2008-07-11 21:57 11699istringstream对象可以绑定一行字符串，然后以空格为 ... -
最小路径覆盖
2008-05-09 02:15 1482给n个自然数，要求穿在尽量少的柱子上，条件是i+j是个完全平方 ... -
筛选法求素数
2008-05-09 02:11 23321 2 3 4 5 6 7 8 9 10 11 12 13 1 ... -
有向图的极大强连通分量算法
2008-05-09 02:08 22221. 对有向图G进行DFS，记录时间戳Ai，形成森林W1 2. ... -
最短路径算法
2008-05-09 02:05 1184单源最短路径： 1. Dijkstra 复杂度取 ... -
最小生成树 MST
2008-05-09 01:53 11961. Kruskal O(ElgV) 思路：每个顶点 ... -
最大子段和 O(n)求解
2008-05-09 01:45 2056设置一个 max=0; //其用来记录非负最大值 对于以下序列 ... -
最长递增子序列
2008-05-09 01:36 966if( a[i] > a[j] ) dp[i] = ... -
最长公共子序列 LCS DP
2008-05-09 01:33 1707一个会“记忆”的矩阵： c[i, j] = ... -
N结点二叉树中M个结点的连通子图个数
2008-04-16 21:31 1257给定一棵有N个结点的二叉树。求它的所有结点数为M的连通子图数目 ... -
主定理
2008-04-16 18:01 908请参看附件图片 -
排序算法—史上最全
2008-04-16 16:37 1498http://baike.baidu.com/view/297 ... -
从n到m中出现多少个1
2008-04-16 15:41 9411. f(n, m): N到M中出现多少个1。 2. g(x ... -
Joseph—约瑟夫环 线性复杂度
2008-04-16 14:59 1717说有n个要被处决的人（编号0~(n-1))，从0开始报 ... -
整数划分
2008-04-16 10:20 1052#include <iostream> usin ...
相关推荐
3. **贪心策略**：虽然0-1背包问题不能通过简单的贪心策略解决，但在某些特殊情况下，例如物品价值和重量成正比时，可以选择按价值/重量比例排序并依次选取，可以得到近似最优解。 4. **分支限界法**：这是一种基于...
尽管0/1背包问题不直接适合分治，但可以通过排序物品（按价值/重量比降序排列）并采用贪心策略来简化问题。对于前半部分物品，尽可能装入；对于后半部分物品，若能装入且不超重，则全部装入。这种方法简单但可能不...
初始化`dp[0] = 0`，表示凑出0元不需要任何硬币。 我们遍历所有可能的硬币面值，对于每个面值`coin`，我们更新`dp[w]`的值，`w`从`coin`到目标金额`target`。如果当前`w`小于`coin`，则`dp[w]`保持不变；如果`w`...
2. **表格型DP**：包括线性DP、二维DP等，如`poj1276`的0-1背包问题。 3. **最优二分检索树**：如`poj1942`。 **六、数学** 1. **组合数学**：包括加法原理、乘法原理、排列组合及递推关系，如`poj1850`的排列组合...
内容概要：本文详细介绍了基于结构不变补偿的电液伺服系统低阶线性主动干扰抑制控制（ADRC）方法的实现过程。首先定义了电液伺服系统的基本参数，并实现了结构不变补偿（SIC）函数，通过补偿非线性项和干扰，将原始系统转化为一阶积分链结构。接着，设计了低阶线性ADRC控制器，包含扩展状态观测器（ESO）和控制律，用于估计系统状态和总干扰，并实现简单有效的控制。文章还展示了系统仿真与对比实验，对比了低阶ADRC与传统PID控制器的性能，证明了ADRC在处理系统非线性和外部干扰方面的优越性。此外，文章深入分析了参数调整与稳定性，提出了频域稳定性分析和b0参数调整方法，确保系统在参数不确定性下的鲁棒稳定性。最后，文章通过综合实验验证了该方法的有效性，并提供了参数敏感性分析和工程实用性指导。 适合人群：具备一定自动化控制基础，特别是对电液伺服系统和主动干扰抑制控制感兴趣的科研人员和工程师。 使用场景及目标：①理解电液伺服系统的建模与控制方法；②掌握低阶线性ADRC的设计原理和实现步骤；③学习如何通过结构不变补偿简化复杂系统的控制设计；④进行系统仿真与实验验证，评估不同控制方法的性能；⑤掌握参数调整与稳定性分析技巧，确保控制系统在实际应用中的可靠性和鲁棒性。 阅读建议：本文内容详尽，涉及多个控制理论和技术细节。读者应首先理解电液伺服系统的基本原理和ADRC的核心思想，然后逐步深入学习SIC补偿、ESO设计、控制律实现等内容。同时，结合提供的代码示例进行实践操作，通过调整参数和运行仿真，加深对理论的理解。对于希望进一步探索的读者，可以关注文中提到的高级话题，如频域稳定性分析、参数敏感性分析等，以提升对系统的全面掌控能力。
蓝桥杯嵌入式
PCB_PCB_2021-01-22_16-58-07_2025-03-02.json
【项目资源】： 适用于从基础到高级的各种项目，特别是在性能要求较高的场景中，比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者，可以从简单的控制台程序开始练习；如果是进阶开发者，可以尝试涉及硬件或网络的项目。 【项目质量】： 所有源码都经过严格测试，可以直接运行。 功能在确认正常工作后才上传。 【适用人群】： 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】： 项目具有较高的学习借鉴价值，也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说，可以在这些基础代码上进行修改和扩展，实现其他功能。 【沟通交流】： 有任何使用上的问题，欢迎随时与博主沟通，博主会及时解答。 鼓励下载和使用，并欢迎大家互相学习，共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等，一切后果由使用者承担。 2. 部分字体以及插图等来自网络，若是侵权请联系删除。
内容概要：汇编语言是一种低级编程语言，它作为计算机硬件与高级语言间的桥梁，使用助记符表示机器指令。起源于20世纪40年代末至50年代初，目的是替代难以理解的机器语言。汇编语言的特点在于高效性和灵活性，可直接与硬件交互，充分利用硬件资源。它广泛应用于操作系统开发（如中断处理、内存管理）、嵌入式系统（如实时控制系统）以及对安全性和可靠性要求极高的软件开发中。学习汇编语言有助于深入了解计算机工作原理，提升程序性能优化、复杂问题调试及高性能软件开发的能力，培养逻辑思维和关注细节的习惯。; 适合人群：对计算机底层原理感兴趣的程序员、计算机科学专业学生或希望深入理解计算机硬件与软件交互机制的人士。; 使用场景及目标：①理解计算机底层工作原理；②提高程序性能优化能力；③增强复杂问题调试技巧；④开发高性能、高可靠性的软件。; 其他说明：尽管现代编程更多使用高级语言，但汇编语言的学习价值依然很高，特别是在涉及硬件交互和性能优化方面。建议学习时结合实际项目进行练习，以加深理解。
【项目资源】： 单片机项目适用于从基础到高级的各种项目，特别是在性能要求较高的场景中，比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者，可以从简单的控制台程序开始练习；如果是进阶开发者，可以尝试涉及硬件或网络的项目。 【项目质量】： 所有源码都经过严格测试，可以直接运行。 功能在确认正常工作后才上传。 【适用人群】： 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】： 项目具有较高的学习借鉴价值，也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说，可以在这些基础代码上进行修改和扩展，实现其他功能。 【沟通交流】： 有任何使用上的问题，欢迎随时与博主沟通，博主会及时解答。 鼓励下载和使用，并欢迎大家互相学习，共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等，一切后果由使用者承担。 2. 部分字体以及插图等来自网络，若是侵权请联系删除。
本书名为《Web Programming for Business: PHP Object-Oriented Programming with Oracle》，由David Paper撰写，主要面向希望在商业环境中解决数据和技术问题的学生。本书采用Oracle作为后端数据库，内容版本中立，即使PHP和Oracle发生变更，书中代码依然有效。书中代码示例清晰，注重解决方案，并详细解释了如何利用XML、RSS和AJAX等技术在商业应用中。章节内容涵盖了数据库功能、安全编程以及数据转换编程。此外，书中还提供了PowerPoint幻灯片、应用考试题目和示例代码的源文件，旨在通过实例教学帮助读者掌握PHP面向对象编程。大卫·佩珀教授拥有德州仪器和IBM等大公司的实际工作经验，目前在美国犹他州立大学教授计算机科学和商业专业。
内容概要：本文详细解析了一个用于电动汽车转弯制动时ABS（防抱死系统）与DYC（横摆力矩控制）协同工作的Simulink模型。模型采用7自由度设计，涵盖纵向、横向、横摆运动及四轮旋转自由度，并引入轮胎魔术公式来精确模拟轮胎力特性。文章重点介绍了ABS系统中的滑移率观测与PID控制策略，以及DYC系统的滑模控制设计，特别是两者之间的协同控制逻辑。通过双移线工况测试验证，该模型能够显著提高车辆稳定性，将横摆角控制在3度以内，并缩短制动距离1.2米。文中还提供了关于模型优化、参数调试的具体建议，以及针对特定工况的仿真技巧。 适合人群：从事车辆控制系统开发的工程师、研究生及对汽车主动安全技术感兴趣的科研人员。 使用场景及目标：①研究ABS与DYC在电动汽车中的协同控制机制；②探索不同路面条件下车辆动态性能优化；③为ESP或TCS系统开发提供参考模型；④比较滑模控制与LQR控制在车辆控制中的应用效果。 阅读建议：建议读者重点关注7自由度模型的设计思路、轮胎魔术公式的实现方式、滑模控制参数调试过程以及ABS和DYC协同控制策略。由于模型涉及较多数学公式和Simulink实现细节，建议结合相关文献深入理解，并通过实际仿真加深认识。
# 基于LVGL图形库的PC模拟器 ## 项目简介 本项目是基于LVGL图形库的PC模拟器。LVGL是为嵌入式系统设计的开源图形库，用于创建嵌入式系统的图形用户界面。该项目将LVGL移植到PC上，让开发者无需嵌入式硬件，就能在PC上进行LVGL应用的开发、调试和测试，节约成本且能提升开发效率。 ## 项目的主要特性和功能 1. 跨平台支持可在Windows、Linux和OSX等操作系统上运行。 2. 图形用户界面模拟借助LVGL图形库的各种GUI组件和工具进行模拟。 3. 模拟输入设备能模拟鼠标和键盘的输入操作。 4. 灵活调试通过PC模拟器开发和调试应用程序，便于查找和修复错误。 5. Docker支持便于在Docker容器中运行和测试项目。 ## 安装使用步骤 假设用户已经下载了本项目的源码文件 ### 安装依赖
【项目资源】： 单片机项目适用于从基础到高级的各种项目，特别是在性能要求较高的场景中，比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者，可以从简单的控制台程序开始练习；如果是进阶开发者，可以尝试涉及硬件或网络的项目。 【项目质量】： 所有源码都经过严格测试，可以直接运行。 功能在确认正常工作后才上传。 【适用人群】： 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】： 项目具有较高的学习借鉴价值，也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说，可以在这些基础代码上进行修改和扩展，实现其他功能。 【沟通交流】： 有任何使用上的问题，欢迎随时与博主沟通，博主会及时解答。 鼓励下载和使用，并欢迎大家互相学习，共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等，一切后果由使用者承担。 2. 部分字体以及插图等来自网络，若是侵权请联系删除。
【项目资源】： 适用于从基础到高级的各种项目，特别是在性能要求较高的场景中，比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者，可以从简单的控制台程序开始练习；如果是进阶开发者，可以尝试涉及硬件或网络的项目。 【项目质量】： 所有源码都经过严格测试，可以直接运行。 功能在确认正常工作后才上传。 【适用人群】： 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】： 项目具有较高的学习借鉴价值，也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说，可以在这些基础代码上进行修改和扩展，实现其他功能。 【沟通交流】： 有任何使用上的问题，欢迎随时与博主沟通，博主会及时解答。 鼓励下载和使用，并欢迎大家互相学习，共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等，一切后果由使用者承担。 2. 部分字体以及插图等来自网络，若是侵权请联系删除。
内容概要：本文介绍了SymPy，一个用于符号数学的Python库。SymPy起源于2007年，由Ondřej Čertík和Aaron Meurer发起，现已发展成一个活跃的开源社区项目。SymPy的核心功能包括符号计算、数学表达式的解析与简化、微积分、线性代数、物理学和工程学应用、可视化、代码生成等。它支持符号变量的创建和基本代数运算，能求解方程、执行符号积分与微分、计算极限与级数、进行矩阵操作等。此外，SymPy在物理问题（如量子力学中的谐振子问题和经典力学中的运动方程）和数学问题（如函数图形和矩阵变换的可视化）的实际应用中表现出色。安装SymPy可通过pip完成，安装后可通过导入库来验证安装是否成功。SymPy与NumPy的区别在于前者专注于符号数学，后者侧重于数值计算。调试SymPy代码时，可以使用print语句、pprint函数、simplify函数以及断点和调试器等工具。 适合人群：对符号数学感兴趣的程序员、研究人员、教师和学生，尤其是那些希望在Python环境中进行数学研究和教育的人群。 使用场景及目标：①用于符号数学计算，如代数运算、微积分、解方程等；②在物理学和工程学中解析和求解微分方程；③结合Matplotlib等库进行数学表达式的可视化；④将符号表达式转换为其他编程语言的代码，适用于高性能计算和嵌入式系统。 阅读建议：由于SymPy涵盖了广泛的数学功能，建议读者从基础功能入手，逐步深入到高级应用。同时，结合实际案例和可视化工具，以更好地理解和掌握SymPy的强大功能。在学习过程中，可以利用提供的调试工具确保代码的正确性。
安装包
# 基于Spring Boot框架的ABrowse基因组浏览器 ## 项目简介 ABrowse是一款轻量级的通用基因组浏览器框架，目标是助力生物学家搭建便捷易用的基因组浏览器。其可视化引擎在浏览器端运行，能为用户带来出色的交互体验。该框架支持GTF、BedGraph、SAM等数据格式以及自定义的存储转录剪接位点的数据格式，数据可通过其提供的接口导入本地mongoDB，开发者还能基于API扩展对更多数据格式的支持。此外，ABrowse支持为同一种数据格式提供多种可视化形式，并且可以借助JavaScript API进一步添加更多可视化方法。软件采用Browser Server架构，后端运用Spring Boot框架，前端由HTML5 + JavaScript实现。 ## 项目的主要特性和功能 1. 多数据格式支持支持GTF、BedGraph、SAM等常见格式以及自定义的转录剪接位点数据格式。
解码 -getitem- 和 -len- - 自定义序列的钥匙