1 public class Knapsack { 2     private final int MIN = Integer.MIN_VALUE; 3  4     @org.junit.Test 5     public void test() { 6         int[] w = {3, 2, 2}; 7         int[] v = {5, 10, 20}; 8         knapsackOptimal(5, w, v); 9     }10 11     /**12      * 01背包-容量压缩13      *14      * @param c      包容量15      * @param weight 各物品质量16      * @param value  各物品价值17      */18     public void knapsackOptimal(int c, int[] weight, int[] value) {19         int n = weight.length; //物品数量20         int[] w = new int[n + 1];21         int[] v = new int[n + 1];22         int[][] G = new int[n + 1][c + 1];23         for (int i = 1; i < n + 1; i++) {24             w[i] = weight[i - 1];25             v[i] = value[i - 1];26         }27 28         //初始化values[0...c]=0————在不超过背包容量的情况下，最多能获得多少价值29         //原因：如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了30         int[] values = new int[c + 1];31         //初始化values[0]=0，其它全为负无穷————解决在恰好装满背包的情况下，最多能获得多少价值的问题32         //原因：只有容量为0的背包可以什么物品都不装就能装满，此时价值为0，其它容量背包均无合法的解，属于未定义的状态，应该被赋值为负无穷33         /*for (int i = 1; i < values.length; i++) {34             values[i] = MIN;35         }*/36 37         for (int i = 1; i < n + 1; i++) {38             for (int t = c; t >= w[i]; t--) {39                 if (values[t] < values[t - w[i]] + v[i]) {40                     values[t] = values[t - w[i]] + v[i];41                     G[i][t] = 1;42                 }43             }44         }45         System.out.println("最大价值为： " + values[c]);46         System.out.print("装入背包的物品编号为： ");47         /*48         输出顺序:逆序输出物品编号49         注意：这里另外开辟数组G[i][v],标记上一个状态的位置50         G[i][v] = 1:表示物品i放入背包了，上一状态为G[i - 1][v - w[i]]51         G[i][v] = 0:表示物品i没有放入背包，上一状态为G[i - 1][v]52         */53         int i = n;54         int j = c;55         while (i > 0) {56             if (G[i][j] == 1) {57                 System.out.print(i + " ");58                 j -= w[i];59             }60             i--;61         }62     }63 }