动态规划：0-1背包问题

1. 方法一

/**
     * 动态规划 0-1背包问题
     *
     * @param weight 物品重量
     * @param w      背包能承受的总重量
     * @return
     */
    public static int knapsack(int[] weight, int w) {
        int n = weight.length;
        boolean[][] states = new boolean[n][w + 1]; // 默认值false
        states[0][0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化
        if (weight[0] <= w) {
            states[0][weight[0]] = true;
        }
        for (int i = 1; i < n; ++i) { // 动态规划状态转移
            for (int j = 0; j <= w; ++j) {// 不把第i个物品放入背包
                if (states[i - 1][j] == true) states[i][j] = true;
            }
            for (int j = 0; j <= w - weight[i]; ++j) {//把第i个物品放入背包
                if (states[i - 1][j] == true) states[i][j + weight[i]] = true;
            }
        }
        int t = 0;
        for (int i = w; i >= 0; --i) { // 输出结果
            if (states[n - 1][i] == true) {
                t = i;
                break;
            }
        }

        int tmp = t;
        java.util.Stack<Integer> stack = new Stack();
        for (int i = n - 1; i >= 0; i--) {
            if (i > 0) {
                if (states[i - 1][tmp] == false && states[i][tmp - weight[i]] == true) {
                    stack.push(i);
                    tmp -= weight[i];
                }
            } else {
                if (t > 0) {
                    stack.push(i);
                }
            }
        }

        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + "，");
        }

        return t;
    }

2. 方法二(改进版本)

    public static int knapsack(int[] weight, int w) {
        int n = weight.length;
        boolean[] states = new boolean[w + 1];
        states[0] = true;
        if (weight[0] <= w) {
            states[weight[0]] = true;
        }
        for (int i = 1; i < n; i++) {
            for (int j = w - weight[i]; j >= 0; j--) {
                if (states[j] == true) {
                    states[j + weight[i]] = true;
                }
            }
        }

        int t = 0;
        for (int i = w; i >= 0; i--) {
            if (states[i] == true) {
                t = i;
                break;
            }
        }

        int tmp = t;
        Stack<Integer> stack = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            if (tmp - weight[i] >= 0 && states[tmp - weight[i]] == true) {
                tmp -= weight[i];
                stack.push(i);
            }
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + "，");
        }

        return t;
    }

3. 背包里价值最大

    public static int knapsack(int[] weight, int[] value, int w) {
        int n = weight.length;
        int[][] states = new int[n][w + 1];
        for (int i = 0; i < states.length; i++) {
            for (int j = 0; j < states[i].length; j++) {
                states[i][j] = -1;
            }
        }
        int maxValue = 0;
        states[0][0] = 0;
        if (weight[0] <= w) {
            states[0][weight[0]] = value[0];
        }
        for (int i = 1; i < n; i++) {
            //不装入背包
            for (int j = 0; j <= w; j++) {
                if (states[i - 1][j] > 0)
                    states[i][j] = states[i - 1][j];
            }
            //装入背包
            for (int j = 0; j <= w - weight[i]; j++) {
                if (states[i - 1][j] >= 0) {
                    int v = states[i - 1][j] + value[i];
                    if (v > states[i][j + weight[i]]) {
                        states[i][j + weight[i]] = v;
                    }
                }
            }
        }

        int p = 0;
        for (int i = 0; i <= w; i++) {
            if (states[n - 1][i] > maxValue) {
                maxValue = states[n - 1][i];
                p = i;
            }
        }

        Stack<Integer> stack = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            if (i > 0) {
                if (states[i - 1][p] == states[i][p]) {

                } else {
                    stack.push(i);
                    p -= weight[i];
                }
            } else {
                if (states[i][p] > 0) {
                    stack.push(i);
                }
            }
        }

        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + "，");
        }

        return maxValue;
    }