0-1背包—DP、暴力、贪心

最简单地：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. }