1.引子
我们人类是一种贪婪的动物，如果给您一个容量一定的背包和一些大小不一的物品，裝到背包里面的物品就归您，遇到这种好事大家一定不会错过，用力塞不一定是最好的办法，用脑子才行，下面就教您如何解决这样的问题，以获得更多的奖品。
2.应用场景
在一个物品向量中找到一个子集满足条件如下 ：
1）这个子集加起来的体积大小不能大于指定阀值
2) 这个物品子集加起来价值大小是向量V中所有满足条件1的子集中最大的
3.分析
背包问题有好多版本，本文只研究0/1版本，即对一个物体要么选用，要么就抛弃，不能将一个物体再继续细分的情况。这种问题最简单的方法就是找出这个向量的所有子集，如同找出幂集中的子集一样，但这种遍历的方法恐怕并不会被聪明的我们所使用，现在举办这些活动的电视台也非常聪明，他们不但要求您能将物品装进去，而且指定操作时间，这样当您慢慢腾腾的装进去倒出来的时候，时间恐怕早就到了，最终您可能一无所获，这可不是我们希望的结果，我们需要使用一些策略：第一次我们可以从大小小于背包容量的物品中随意挑取一个，这样可以尽量争取时间，选取第一个后的每一个我们希望其都是最优的，这样能节省一定的时间。假设有这么一组物品，其大小和价值如下表所示：
| 物品编号 |
大小 |
价值 |
| 1 |
2 |
1 |
| 2 |
3 |
4 |
| 3 |
4 |
3 |
| 4 |
5 |
6 |
| 5 |
6 |
8 |
给我们一个容量为12的背包，让我们装上面这些物品，我们可以用下面的方法来解决寻找最优组合的问题
建立一个二围数组，数组包括n个行(n为物品数量)和capcity+1列
首先我们对第一个物品进行取舍，因为物品1大小为2，先将物品1加入背包，物品1的大小为2，则cap>=2的时候能容纳item1，这时候背包里面物品的价值为item1.Value=1,得到以下数组
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
| 0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
接下来处理物品1和物品2的子集，item2的大小为3，则只有cap=3的时候才能容纳item2,当cap=3的时候讲好能容纳item2,此时背包里面价值item2.value=4,且剩余空间为0，当cap=4的时候，能容纳item2，且剩余空间为1，不能容item1,当cap=5的时候，可以容纳item1+item2,此时的价值为1+4 =5，得到第二行
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
| 0 |
0 |
1 |
4 |
4 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
5 |
下面分析物品三，物品二，物品一的子集，物品三的大小为4，当cap=4的时候就能容纳item3,但此时背包里面的价值为3，明显小于上一行中的cap=4的价值（3<4),所以cap=4时不能将item3放进去，所以第三行的4位置应该和第二行的4位置一致，当cap=5的时候能够容纳item3,且剩余空间为1，和cap=4情况一样，拷贝上一行同一位置的值，当cap=6，放置item3后剩余2，能容item1和item4,二者的总价值:1+3=4<5，故拷贝上一行同位置的值，cap=7的时候，能容item2+item3，总价值大小为7,大于>5，故cap=8的时的值为7，cap=9的时候仍能容难item3+item2,value=7，cap=8的时候，能容纳item1+item2+item3,且总价值大小为8，大于上一行同位置的值，故cap>=9时候，总价值大小为8,第三行：
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
| 0 |
0 |
1 |
4 |
4 |
5 |
5 |
7 |
7 |
8 |
8 |
8 |
8 |
按照这样的逻辑可以得到下面两列，最后二围数组是
0，0，1，1，1，1，1，1，1，1，1，1，1
0，0，1，4，4，5，5，5，5，5，5，5，5
0，0，1，4，4，5，5，7，7，8，8，8，8
0，0，1，4，4，6，6，7，10，10，11，11，13
0，0，1，4，4，6，8，8，10，12，12，14，14
得到这样的数组之后，我们需要作的是根据这个二围数组来产生最优物品子集，方法为
从第len行开始，比较最后一行cap索引位置的值是否大于上一行同一位置的值，如先比较第五行位置12的值（14）与第四行位置12的值(13)，因为14!=13,所以item5放置到最优集合中，item5的大小为6，故比较第四行cap-6=6的位置上的值与上一行同一位置上值得大小，因为6！= 5,所以item4能放置到最优集合，下一步要比较的位置cap = 6-item4.Size=6-5=1,第三行位置1与第二行位置1相同，故item3不能放置到最优集合，第二行和第一行第一个位置上的值也一样，所以item2也不能放置进去，最后判断item1是否应该在最优集合，item5+item4后，剩余空间为1，不能容纳item1,故最优集合为{item4,item5};
综合上面的分析，我们可以得到这样的一个处理流程
1) 首先建立一个nx(cap+1)的二围数组
2) 第一行从尝试选择第一个物品开始
3) 对于以后的行，对于每个容量1<=cap<=capacity，首先拷贝上一行同一位置的值下来，如果itemi.Size<=cap并且上一行(cap-itemi.Size)位置上的值与itemi.Value的 和(tempMax)大于拷贝下来的值的话，就将拷贝下来的值替换为上一行(cap-itemi.Size)位置上的值与itemi.Value的 和（tempMax）
4) 得到完整数组之后，我们既可以根据数组来确定最优集合了，首先从最后一样最后位置开始，和上一行的同一位置进行比较，如果相同，则该行对应索引的物品不能放到背包中，否则放到背包，并且开始比较上一行与 上上一行在当前背包剩余空间索引出的值，如不等，则对应物品可放置，如此，直到处理到第二行和第一行的比对完成，然后根据当前背包剩余容量与第一个物品的大小比对来确定物品一是否能放置到背包中
5. 结论
上文采用的是动态编程的方法来处理此类背包问题，上面的文章中兄弟们也提到了用递归算法时间复杂度的问题，认为递归算法效率比较低下，这种疑问无可厚非，但递归算法也有它的优点，很多问题都能用递归来解决，我目前学习的就是用这种算法来解决一些常见问题，对于其他算法，比如此问题也可以采用贪婪算法，遗传算法等得以更好的解决，但本文暂不作讨论，以后有时间，一定将这些算法加以实现并详细比较其优劣。
0-1背包问题的DP解和暴力解 收藏
原文地址：
http://blog.csdn.net/iJuliet/archive/2008/12/19/3560993.aspx
view plaincopy to clipboardprint?
最简单地：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. }
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/super_chris/archive/2009/09/08/4532323.aspx