1.引子
我們?nèi)祟愂且环N貪婪的動物，如果給您一個容量一定的背包和一些大小不一的物品，裝到背包里面的物品就歸您，遇到這種好事大家一定不會錯過，用力塞不一定是最好的辦法，用腦子才行，下面就教您如何解決這樣的問題，以獲得更多的獎品。
2.應(yīng)用場景
在一個物品向量中找到一個子集滿足條件如下 ：
1）這個子集加起來的體積大小不能大于指定閥值
2) 這個物品子集加起來價值大小是向量V中所有滿足條件1的子集中最大的
3.分析
背包問題有好多版本，本文只研究0/1版本，即對一個物體要么選用，要么就拋棄，不能將一個物體再繼續(xù)細(xì)分的情況。這種問題最簡單的方法就是找出這個向量的所有子集，如同找出冪集中的子集一樣，但這種遍歷的方法恐怕并不會被聰明的我們所使用，現(xiàn)在舉辦這些活動的電視臺也非常聰明，他們不但要求您能將物品裝進去，而且指定操作時間，這樣當(dāng)您慢慢騰騰的裝進去倒出來的時候，時間恐怕早就到了，最終您可能一無所獲，這可不是我們希望的結(jié)果，我們需要使用一些策略：第一次我們可以從大小小于背包容量的物品中隨意挑取一個，這樣可以盡量爭取時間，選取第一個后的每一個我們希望其都是最優(yōu)的，這樣能節(jié)省一定的時間。假設(shè)有這么一組物品，其大小和價值如下表所示：
| 物品編號 |
大小 |
價值 |
| 1 |
2 |
1 |
| 2 |
3 |
4 |
| 3 |
4 |
3 |
| 4 |
5 |
6 |
| 5 |
6 |
8 |
給我們一個容量為12的背包，讓我們裝上面這些物品，我們可以用下面的方法來解決尋找最優(yōu)組合的問題
建立一個二圍數(shù)組，數(shù)組包括n個行(n為物品數(shù)量)和capcity+1列
首先我們對第一個物品進行取舍，因為物品1大小為2，先將物品1加入背包，物品1的大小為2，則cap>=2的時候能容納item1，這時候背包里面物品的價值為item1.Value=1,得到以下數(shù)組
| 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,當(dāng)cap=3的時候講好能容納item2,此時背包里面價值item2.value=4,且剩余空間為0，當(dāng)cap=4的時候，能容納item2，且剩余空間為1，不能容item1,當(dāng)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，當(dāng)cap=4的時候就能容納item3,但此時背包里面的價值為3，明顯小于上一行中的cap=4的價值（3<4),所以cap=4時不能將item3放進去，所以第三行的4位置應(yīng)該和第二行的4位置一致，當(dāng)cap=5的時候能夠容納item3,且剩余空間為1，和cap=4情況一樣，拷貝上一行同一位置的值，當(dāng)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 |
按照這樣的邏輯可以得到下面兩列，最后二圍數(shù)組是
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
得到這樣的數(shù)組之后，我們需要作的是根據(jù)這個二圍數(shù)組來產(chǎn)生最優(yōu)物品子集，方法為
從第len行開始，比較最后一行cap索引位置的值是否大于上一行同一位置的值，如先比較第五行位置12的值（14）與第四行位置12的值(13)，因為14!=13,所以item5放置到最優(yōu)集合中，item5的大小為6，故比較第四行cap-6=6的位置上的值與上一行同一位置上值得大小，因為6！= 5,所以item4能放置到最優(yōu)集合，下一步要比較的位置cap = 6-item4.Size=6-5=1,第三行位置1與第二行位置1相同，故item3不能放置到最優(yōu)集合，第二行和第一行第一個位置上的值也一樣，所以item2也不能放置進去，最后判斷item1是否應(yīng)該在最優(yōu)集合，item5+item4后，剩余空間為1，不能容納item1,故最優(yōu)集合為{item4,item5};
綜合上面的分析，我們可以得到這樣的一個處理流程
1) 首先建立一個nx(cap+1)的二圍數(shù)組
2) 第一行從嘗試選擇第一個物品開始
3) 對于以后的行，對于每個容量1<=cap<=capacity，首先拷貝上一行同一位置的值下來，如果itemi.Size<=cap并且上一行(cap-itemi.Size)位置上的值與itemi.Value的 和(tempMax)大于拷貝下來的值的話，就將拷貝下來的值替換為上一行(cap-itemi.Size)位置上的值與itemi.Value的 和（tempMax）
4) 得到完整數(shù)組之后，我們既可以根據(jù)數(shù)組來確定最優(yōu)集合了，首先從最后一樣最后位置開始，和上一行的同一位置進行比較，如果相同，則該行對應(yīng)索引的物品不能放到背包中，否則放到背包，并且開始比較上一行與 上上一行在當(dāng)前背包剩余空間索引出的值，如不等，則對應(yīng)物品可放置，如此，直到處理到第二行和第一行的比對完成，然后根據(jù)當(dāng)前背包剩余容量與第一個物品的大小比對來確定物品一是否能放置到背包中
5. 結(jié)論
上文采用的是動態(tài)編程的方法來處理此類背包問題，上面的文章中兄弟們也提到了用遞歸算法時間復(fù)雜度的問題，認(rèn)為遞歸算法效率比較低下，這種疑問無可厚非，但遞歸算法也有它的優(yōu)點，很多問題都能用遞歸來解決，我目前學(xué)習(xí)的就是用這種算法來解決一些常見問題，對于其他算法，比如此問題也可以采用貪婪算法，遺傳算法等得以更好的解決，但本文暫不作討論，以后有時間，一定將這些算法加以實現(xiàn)并詳細(xì)比較其優(yōu)劣。
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 。問:應(yīng)該如何選擇裝入背包中的物品，
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背包問題是一個特殊的整數(shù)規(guī)劃問題。
17. *
18. ***********************************************************/
19.
20.
21. public class BagZeroOne {
22.
23. /**********************************************************************
24. * 動態(tài)規(guī)劃解 (Dynamic Programming)
25. *
26. * @param v in the 物品價值數(shù)組
27. * @param w in the 物品重量數(shù)組
28. * @param c in the 背包的容量
29. * @param m out the 最優(yōu)值數(shù)組，m[i][j]即背包容量為j,可選物品為 i, i + 1, ... , n 時0-1背包問題的最優(yōu)值
30. *
31. * 由于0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算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 最優(yōu)值數(shù)組
71. * @param w in the 重量數(shù)組
72. * @param c in the 背包容量
73. * @param x out the 物品選擇數(shù)組 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. //應(yīng)該的輸出
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, 當(dāng)前選擇已經(jīng)達到的重量之和 tw, 本方案可能達到的總價值 tv)
121. * {
122. * //考慮物品 i 包含在當(dāng)前方案的可能性
123. * if (包含物品 i 是可接受的)
124. * {
125. * 將物品 i 包含在當(dāng)前方案中；
126. * if (i < n - 1)
127. * try(i + 1, tw + w[i], tv);
128. * else //又是一個完整方案，因它比前面的方案要好，以它作為最佳方案
129. * 以當(dāng)前方案作為臨時最佳方案保存
130. * 恢復(fù)物品 i 不包含在內(nèi)的狀態(tài)
131. * }
132. * //考慮物品 i 不包含在當(dāng)前方案中的可能性
133. * if (不包含物品 i 僅是可考慮的)
134. * {
135. * if (i < n - 1)
136. * try(i + 1, tw, tv - v[i]);
137. * else //又是一個完整方案，因它比前面的方案要好，以它作為最佳方案
138. * 以當(dāng)前方案作為臨時最佳方案保存
139. * }
140. * }
141. ******************************************************************************/
142.
143. private static int[] w; //重量
144. private static int[] v; //價值
145. private static int[] x; //最優(yōu)解
146. private static int[] opt; //有效解
147. private static int c; //背包容量
148. private static int maxv; //最優(yōu)值
149.
150. public static void find(int i, int tw, int tv) {
151. //考慮物品 i 包含在當(dāng)前方案中的可能性
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 不包含在當(dāng)前方案中的可能性
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. //當(dāng)前候選解中各物品的考慮和選擇狀態(tài)，以及置該物品候選解的狀態(tài)
211. private static int[] flag; //物品的考慮狀態(tài)：0.不選;1.將被考慮;2.曾被選中
212. private static int[] twe; //已經(jīng)達到的總重量
213. private static int[] tve; //期望的總價值
214.
215. private static int maxw; //背包容量
216. private static int[] cop; //臨時最佳解的物品選擇方案，當(dāng)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博客，轉(zhuǎn)載請標(biāo)明出處：http://blog.csdn.net/super_chris/archive/2009/09/08/4532323.aspx