0-1背包—DP、暴力、贪心
最简单地：v是空间，w是价值，要求总价值最大dp = max {dp] + w};//自顶向下；
//自底向上
1./**********************************************************
2. * 0-1背包问题
3. *
4. * 问题描述：
5. * 给定n种物品和一背包。物品 i 的重量是 w ，其价值为
6. * v ，背包的容量为 c 。问:应该如何选择装入背包中的物品，
7. * 使得装入背包中物品的总价值最大？
8. *
9. * 在选择装入背包中的物品时，对每种物品 i 只有两种选择，
10. * 即装入或不装入背包。不能将物品 i 装入背包多次，也不能只
11. * 装入部分的物品 i 。因此，该问题称为 0-1 背包问题。
12. *
13. * 此问题的形式化描述为，给定 c > 0, w > 0, v > 0
14. * 1 <= i <= n ,要求找出 n 元 0-1 向量 x, 其中x
15. * 等于0或1,使得对 w * x 求和小于等于 c ，并且 v *
16. * x达到最大。因此，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即背包容量为j,可选物品为 i, i + 1, ... , n 时0-1背包问题的最优值
30. *
31. * 由于0-1背包问题的最优子结构性质，可以建立计算m的递归式如下：
32. * / max{m), m] + v} j >= w
33. * m /
34. * \
35. * \ m 0 <= j < w
36. *
37. * / v j >= w
38. * m /
39. * \
40. * \ 0 0 <= j < w
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 - 1, c);
46. for (int j = 0; j <= jMax; j++) {
47. m = 0;
48. }
49. for (int j = w; j <= c; j++) {
50. m = v;
51. }
52. for (int i = n - 1; i > 0; i--) {
53. jMax = Math.min(w - 1, c);
54. for (int j = 0; j <= jMax; j++) {
55. m = m;
56. }
57. for (int j = w; j <= c; j++) {
58. m = Math.max(m, m] + v);
59. }
60. }
61. /*
62. m = m;
63. if (c >= w) {
64. m = Math.max(m, m] + v);
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 == 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 == m) {
79. x = 0; //不选物品 i
80. } else {
81. x = 1; //选择物品 i
82. c -= w; //剩余容量
83. }
84. }
85. x = (m > 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;
101. int[] x = new int;
102.
103.
104. knapsack(v, w, c, m);
105. trackback(m, w, c, x);
106.
107. if (m == 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, 价值 v
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, 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);
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 <= c) { //包含物品 i 是可以接受的
153.opt = 1;
154. if (i < w.length - 1) {
155. find(i + 1, tw + w, tv);
156. } else { //又是一个完整方案，因它比前面的方案好，以它作为最佳方案
157. for (int j = 0; j < x.length; j++) {
158. x = opt;
159. }
160. maxv = tv;
161. }
162. opt = 0;
163. }
164. //考虑物品 i 不包含在当前方案中的可能性
165. if (tv - v > maxv) { //不包含物品 i 是可以考虑的
166. if (i < w.length - 1) {
167. find(i + 1, tw, tv - v);
168. } else { //又是一个完整方案，因它比前面的方案好，以它作为最佳方案
169. for (int j = 0; j < x.length; j++) {
170. x = opt;
171. }
172. maxv = tv - v;
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;
185. opt = new int;
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 为 1 时，物品 i 在解中
217.
218. //将考虑物品 i
219. private static void next(int i, int tw, int tv) {
220. flag = 1;
221. twe = tw;
222. tve = 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;
236. tw = twe;
237. tv = tve;
238. switch (f) {
239. case 0: //回退
240. i--;
241. break;
242.
243. case 1: //考虑被选中
244. flag++;
245. if (tw + w <= maxw) { //选中可行吗？
246. if (i < n - 1) {
247. next(i + 1, tw + w, tv);
248. i++;
249. } else {
250. maxv = tv;
251. for (k = 0; k < n; k++) {
252. cop = ((flag != 0)? 1 : 0);
253. }
254. }
255. }
256. break;
257.
258. default: //flag等于2
259. flag = 0;
260. if (tv - v > maxv) { //不选物品 i 可行吗？
261. if (i < n - 1) {
262. next(i + 1, tw, tv - v);
263. i++;
264. } else {
265. maxv = tv - v;
266. for (k = 0; k < n; k++) {
267. cop = ((flag != 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;
287.
288. flag = new int;
289. twe = new int;
290. tve = new int;
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. }
页:
[1]