动态规划--背包问题

一个背包的总容量为V，现在有N类物品，第i类物品的重量为weight[i],价值为value[i]。那么往该背包里装东西，怎样装才能使得最终包内物品的总价值最大？

0-1背包

每类物品最多只能装一次

    /**
     * 0-1背包问题
     *
     * 根据动态规划网格图，制定价值矩阵，第n个物品在v容量小的价值
     * dp[i][j] = (dp[i-1][j] > (dp[i-1][j-weight[i -1]]+value[i-1]))
     * ? dp[i-1][j]:(dp[i-1][j-weight[i-1]]+value[i-1])
     *
     * @param v      背包容量
     * @param n      物品种类
     * @param weight 物品重量
     * @param value  物品价值
     * @return
     */
    public static String zeroOnePack(int v, int n, int[] weight, int[] value) {

        //dp的数值，表示价值总和
        int[][] dp = new int[n + 1][v + 1];
        //i是物品，j是容量
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= v; j++) {
                //判断背包的重量是否超重，超重的情况下，最大价值，为上一个最大价值。
                if (weight[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }
                
                //背包的当前容量的最大价值，与装入当前物品+恰能装进当前物品的容量的最大值。
                if (dp[i - 1][j] > dp[i - 1][j - weight[i - 1]] + value[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j - weight[i - 1]] + value[i - 1];
                }

            }

        }

        int j = v;
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = n; i > 0; i--) {
            if (dp[i][j] > dp[i - 1][j]) {
                stringBuilder.append(i);
                j = j - weight[i - 1];
            }
        }

        return stringBuilder.toString();

    }

多重背包问题

物品数量有限制

    public static int manyPack(int v, int n, int[] weight, int[] value, int[] num) {
        //dp的数值，表示价值总和
        int[][] dp = new int[n + 1][v + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= v; j++) {

                if (weight[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }

                //判断该物品在什么数量的情况下价值最大
                int maxV = Math.min(num[i - 1], j / weight[i - 1]);
                for (int k = 0; k <= maxV; k++) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - k * weight[i - 1]] + k * value[i - 1]);
                }

            }

        }

        return dp[n][v];
    }

完全背包问题

每个物品数量无限制

    /**
     * 完全背包问题
     * 每个物品数量无限制
     *
     * 考虑di N行时，n产品可以考虑继续加入
     * dp[i][j] = (dp[i-1][j] > (dp[i][j-weight[i -1]]+value[i-1]))
     * ? dp[i-1][j]:(dp[i][j-weight[i-1]]+value[i-1])
     *
     * @param v
     * @param n
     * @param weight
     * @param value
     * @return
     */
    public static int completePack(int v, int n, int[] weight, int[] value) {

        //dp的数值，表示价值总和
        int[][] dp = new int[n + 1][v + 1];

        for (int i = 1; i <= n; i++) {

            for (int j = 1; j <= v; j++) {

                if (weight[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }
                //当前物品加入判断价值行列
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);

            }

        }

        return dp[n][v];

    }