算法-最优解问题 0-1背包

问题

问题描述

一个可放总重量为 W 的背包和 N 个物品。每个物品，有重量 w 和价值 v 两个属性，那么第 i 个物品的重量为 w[i]，价值为 v[i]。现在用这个背包装物品，问最多能装的价值是多少？

示例：

输入：W = 5, N = 3, w = [3, 2, 1], v = [5, 2, 3]

输出：8

解释：选择 i=0 和 i=2 这两件物品装进背包。它们的总重量 4 小于 W，同时可以获得最大价值 8。

分析

0-1背包是个典型获取最优解的问题，也是经典的动态规划入门问题。

初始化状态

背包物品数量为0，和容量为0 时，是初始状态。
状态参数

背包内的物品数量 N 和背包还能装下的重量 W，就是这个动态规划问题的状态参数。
决策

每一个物品，是放入背包还是不放入背包。取这俩最大值。
备忘录

dp[i][j] ： i 表示第几个物品，j 表示还能放的容量，值自然就是最大价值

动态规划-代码

public class ZeroOneBag {
    public static void main(String[] args) {
        int[] wt = new int[]{2, 1, 3};
        int[] val = {4, 2, 5};

        int nums = 3;
        int weight = 4;

        int i = maxValue(weight, nums, wt, val);
        System.out.println(i);
    }

    static int maxValue(int weights, int numbers, int[] wt, int[] val) {
        /**
         * 初始 dp[0][xxx] = 0
         * 初始 dp[xxx][0] = 0
         * 遍历从下标 1 开始
         */
        int[][] dp = new int[numbers + 1][weights + 1];

        for (int i = 1; i <= numbers; i++) {
            // 把当下物品，对应的所有重量（从1到最大支持重量）都走一遍。等于要穷举所有最优dp[i][w]
            // 当下物品，能重用之前的物品选择，不能选之后的
            // w 指最大容量 
            for (int w = 1; w <= weights; w++) {
                // 当前i物品重量超过了w,这种情况下只能选择不装⼊ i 物品
                if (wt[i - 1] > w) {
                    dp[i][w] = dp[i - 1][w];
                } else {
                    // i 物品装⼊ 还是 不装⼊，择优
                    dp[i][w] = Math.max(dp[i - 1][w - wt[i - 1]] + val[i - 1],
                            dp[i - 1][w]);
                }
            }
        }

        // 打印dp数组
        for (int i = 1; i <= numbers; i++) {
            for (int w = 1; w <= weights; w++) {
                System.out.println("dp[" + i + "][" + w + "]=" + dp[i][w]);
            }
        }

        // dp 最后这个是最大的
        return dp[numbers][weights];
    }

}

排列组合思路-代码

组合的思路：

通过找到每个物品的索引下标组合，过滤超过最大重量的指标得出所有可能下标组合。
计算每个组合下，最大的价值

public class Test {

    static int maxWeight = 5;
    static int[] weights = {3, 2, 1};
    static int[] values = {5, 2, 3};

    static List<List<Integer>> result = new LinkedList<>();
    static LinkedList<Integer> track = new LinkedList<>();
    
    /**
     * W = 5, N = 3, w = [3, 2, 1], v = [5, 2, 3]
     *
     * @param args
     */
    public static void main(String[] args) {

        int[] indexs = new int[weights.length];

        for (int i = 0; i < weights.length; i++) {
            indexs[i] = i;
        }

        int maxValue = 0;

        // 计算所有可能的 下标组合
        backtrace(indexs, 0);

        System.out.println(result);

        for (int i = 0; i < result.size(); i++) {
            int tmp = 0;
            // 索引下标找到对应价值 累加
            for (int j = 0; j < result.get(i).size(); j++) {
                tmp += values[result.get(i).get(j)];
            }

            if (tmp > maxValue) {
                maxValue = tmp;
            }

        }

        System.out.println(maxValue);

    }

    static void backtrace(int[] arr, int start) {
        // 累计重量少于最大重量的所有下标组合
        if (satisfy()) {
            result.add(new LinkedList<>(track));
        }
        for (int i = start; i < arr.length; i++) {

            track.add(arr[i]);

            backtrace(arr, i + 1);

            track.removeLast();

        }
    }

    static boolean satisfy() {
        int total = 0;
        for (int i = 0; i < track.size(); i++) {
            total += weights[track.get(i)];
            if (total > maxWeight) {
                return false;
            }
        }
        return true;
    }


}

算法