bagzeroone.java

java语言实现动态规划求解0-1背包问题。

 
public class BagZeroOne { 
  
        /********************************************************************** 
        *                        动态规划解 (Dynamic Programming) 
        *         
        *        @param v        in        the 物品价值数组 
        *        @param w        in        the 物品重量数组 
        *        @param c        in        the 背包的容量 
        *        @param m        out        the 最优值数组，m[i][j]即背包容量为j,可选物品为 i, i + 1, ... , n 时0-1背包问题的最优值 
        *         
        *        由于0-1背包问题的最优子结构性质，可以建立计算m[i][j]的递归式如下： 
        *                         / max{m[i + 1][j]), m[i + 1][j - w[i]] + v[i]}                j >= w[i]         
        *        m[i][j]       / 
        *                        \ 
        *                          \ m[i + 1][j]                                                         0 <= j < w[i] 
        * 
        *                        / v[n]                                                                    j >= w[n] 
        *        m[n][j]    / 
        *                      \ 
        *                        \ 0                                                                        0 <= j < w[n] 
        * 
        **********************************************************************/ 
    public static void knapsack(int[] v, int[] w, int c, int[][] m) { 
                int n = v.length - 1; 
                int jMax = Math.min(w[n] - 1, c); 
                for (int j = 0; j <= jMax; j++) { 
                    m[n][j] = 0; 
                } 
                for (int j = w[n]; j <= c; j++) { 
                    m[n][j] = v[n]; 
                } 
                for (int i = n - 1; i > 0; i--) { 
                    jMax = Math.min(w[i] - 1, c); 
                        for (int j = 0; j <= jMax; j++) { 
                            m[i][j] = m[i + 1][j]; 
                           // if(i==1){System.out.println(m[i][j]+"A");}
                            
                        } 
                        for (int j = w[i]; j <= c; j++) { 
                            m[i][j] = Math.max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]); 
                           // if(i==1){System.out.println(m[i][j]+"B");}
                        } 
                } 
                /*System.out.println("=========================");
                System.out.println(m[1][c]);
                m[1][c] = m[2][c]; 
                System.out.println(m[1][c]);
                if (c >= w[1]) { 
                    m[1][c] = Math.max(m[1][c], m[2][c - w[1]] + v[1]); 
                } 
                System.out.println(m[1][c]);
                //debug-info
                */
                
        } 
  
        /** 
        *        @param        m        in        the 最优值数组 
        *        @param        w        in        the 重量数组          
        *        @param        c        in        the 背包容量 
        *        @param        x        out        the 物品选择数组 if x[i] == 1 则选物品 i, 否则不选 
        **/ 
        public static void trackback(int[][] m, int[] w, int c, int[] x) { 
                int n = w.length - 1; 
                for (int i = 1; i < n; i++) { 
                    if (m[i][c] == m[i + 1][c]) { 
                        x[i] = 0;                //不选物品 i  
                    } else { 
                        x[i] = 1;                //选择物品 i 
                                c -= w[i];                //剩余容量 
                    } 
                } 
                x[n] = (m[n][c] > 0)? 1: 0; 
        } 
  
        public static void main(String[] args) { 
                System.out.print("1. --- testDynamicProgramming      ---> "); 
                //输入 
                int c = 7; 
                int[] w = {0, 5, 3, 2, 1}; 
                int[] v = {0, 4, 4, 3, 1}; 
                 
                //应该的输出 
                int expectedVMax = 8; 
                int[] expectedX = {0, 0, 1, 1, 1}; 
                 
                //程序运行时变量 
                int[][] m = new int[w.length][c + 1]; 
                int[] x = new int[w.length]; 
  
  
                knapsack(v, w, c, m); 
                trackback(m, w, c, x); 
                 
                if (m[1][c] == expectedVMax && java.util.Arrays.equals(x, expectedX)) { 
                    System.out.println("Test success!"); 
                } else { 
                    System.out.println("Test fail!"); 
                } 
        } 
}