算法设计与分析 3.9 0-1背包问题

1. /**********************************************************
2. *        3.9        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. }