1. // 模型1：从左向右尝试模型
    3. /**
    4.  * 背包问题
    5.  */
    6. public class Code01_Knapsack {
    8.     // 所有的货，重量和价值，都在w和v数组里
    9.     // 为了方便，其中没有负数
    10.     // bag背包容量，不能超过这个载重
    11.     // 返回：不超重的情况下，能够得到的最大价值
    13.     /**
    14.      *
    15.      * @param w  货物数组
    16.      * @param v  重量数组
    17.      * @param bag  背包最大载重
    18.      * @return  不超重的情况下能够得到的最大价值
    19.      */
    20.     public static int maxValue(int[] w, int[] v, int bag) {
    21.         // 特殊边界的情况
    22.         if (w == null || v == null || w.length != v.length || w.length == 0) {
    23.             return 0;
    24.         }
    25.         // 尝试函数！从0号开始向右选择
    26.         return process(w, v, 0, bag);
    27.     }
    29.     // index 0~N
    30.     // rest 负~bag
    31.     /**
    32.      * 方法1：暴力递归
    33.      * @param w  重量
    34.      * @param v  价值
    35.      * @param index  当前来到index位置
    36.      * @param rest   剩余背包容量
    37.      * @return
    38.      */
    39.     // 从左向右尝试，当前来到了index位置。不考虑index之前的信息
    40.     public static int process(int[] w, int[] v, int index, int rest) {
    42.         // 无效解设置，上游在使用时需要进行判断。
    43.         if (rest < 0) {  // 背包为0时有可能装的，如规定，重为0 价值100，
    44.             return -1;
    45.         }
    46.         // 越界位置，没有货了
    47.         if (index == w.length) {
    48.             return 0;
    49.         }
    51.         // 有货，index位置的货物，bag有空间
    53.         // 可能性1：不要当前的货，背包剩余容量变，直接考虑下一个位置
    54.         int p1 = process(w, v, index + 1, rest);
    56.         // 可能性2：要当前的货
    57.         int p2 = 0;
    58.         int next = process(w, v, index + 1, rest - w[index]);
    59.         // 背包不越界的情况下。
    60.         if (next != -1) {
    61.             p2 = v[index] + next;
    62.         }
    63.         return Math.max(p1, p2);
    64.     }
    66.     /**
    67.      * 方式2：动态规划
    68.      *
    69.      * 根据暴力递归可以发现，动态变化的参数只有 index和rest
    70.      *     index 的范围为 0-N  在递归中N为 basecase
    71.      *     rest  的范围为 某个负数 - bag  0 - bag
    72.      *
    73.      */
    74.     public static int dp(int[] w, int[] v, int bag) {
    76.         if (w == null || v == null || w.length != v.length || w.length == 0) {
    77.             return 0;
    78.         }
    80.         int N = w.length;
    81.         int[][] dp = new int[N + 1][bag + 1];
    83.         for (int index = N - 1; index >= 0; index--) {  // 从边界开始
    84.             for (int rest = 0; rest <= bag; rest++) {
    85.                 int p1 = dp[index + 1][rest];
    86.                 int p2 = 0;
    87.                 int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];
    88.                 if (next != -1) {
    89.                     p2 = v[index] + next;
    90.                 }
    91.                 dp[index][rest] = Math.max(p1, p2);
    92.             }
    93.         }
    94.         return dp[0][bag];
    95.     }
    97.     public static void main(String[] args) {
    98.         int[] weights = { 3, 2, 4, 7, 3, 1, 7 };
    99.         int[] values = { 5, 6, 3, 19, 12, 4, 2 };
    100.         int bag = 15;
    101.         System.out.println(maxValue(weights, values, bag));
    102.         System.out.println(dp(weights, values, bag));
    103.     }
    105. }