算法：背包问题

一、题目

背包问题指的是给定2个数组，分别表示一组物品的容量和价值。给定一个背包容量。问在不超过背包容量的前提下能装的物品的最大价值。

背包问题细分有：

1. 01背包问题
2. 完全背包问题
3. 多重背包问题
4. 其他组合背包问题

主要区分在放入物品的数量的限制上。比如01背包问题只能放或者不放1个；完全背包不限制数量；多重背包限制指定数量等。

实际面试场景中都是背包问题的变种，考察的是掌握背包问题在实际场景中的灵活运用。

本文主要介绍01背包问题和完全背包问题。

二、输入

1. 两个相同大小的数组。数组长度对应物品的数量，数组分别对应物品的容量和价值。
2. 待放入物品的背包总容量
3. 物品的数量（可选）

   注意物品的容量有的地方也理解为重量，两者可以互换

三、输出

装入物品的最大价值

四、示例

输入：
int[] w = new int[]{1, 3, 4}; //物品重量
int[] v = new int[]{15, 20, 30};// 物品价值
int n = 3; // 物品数
int c = 4; // 背包容量

输出：
35

五、题解

1. 背包问题大家都知道是动态规划的经典案例。动态规划本质是从遍历所有解找最优子结构，重复子问题降低复杂度。动态规划解答前最好了解暴搜遍历的方法。对应这里的是回溯算法（选还是不选）
2. 动态规划解法先从2维动态数组理解，再考虑一维滚动数组的优化
3. dp[i][j]表示从0~i件物品中选择，背包容量不超过j时背包的最大价值
4. dp[j]表示背包容量不超过j时背包的最大价值
5. 01背包和完全背包的转移方程有小的差别，原因是完全背包中同一个物品可以多次选择。
   01背包：dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]；
   完全背包：dp[i][j] = Math.max(dp[i-1][j], dp[i][j-w[i]] + v[i]
6. 二维动态数组优化为一维数组时需要注意遍历的顺序。01背包问题需要从背包容量最大值到最小值，避免同一件物品被重复计算（放入包中）。二维动态数组没有这个问题，因为第i-1个物品对应的dp值已经被固化，不会被覆盖了
7. 背包问题2层循环一般外层遍历物品，内层遍历背包容量。对于2维动态数组2层循环遍历顺序影响不大；对于1维动态数组解决01背包问题要求外层先遍历物品

5.1 01背包 Java 实现

package org.stone.study.algo.dp;

/**
 * 01背包问题
 */
public class Knapsack_01_Problem {

    public static void main(String[] args) {
/*        int[] w = {2, 2, 6, 5, 4};
        int[] v = {6, 3, 5, 4, 6};
        int c = 10;*/
        int[] w = {1, 3, 4};
        int[] v = {15, 20, 30};
        int c = 4;
        // 15
        // 35
        System.out.println(knapsack_01(w, v, c));
    }

    /**
     * 0/1背包问题：暴力解法和动态规划解法
     */
    public static int knapsack_01(int[] w, int[] v, int c) {
        // 暴力回溯解法
        // return backtrack(w, v, c, 0);

        // 动态规划解法：二维dp数组
        // return dp_01(w, v, c);

        // 动态规划解法：一维dp数组
        return dp_01_rolling_array(w, v, c);
    }

    /**
     * 0/1背包问题：动态规划解法 - 二维dp数组
     */
    private static int dp_01(int[] w, int[] v, int c) {
        int n = w.length;
        // 定义dp数组，dp[i][j]表示前i个物品，背包容量为j时（不超过j）的最大价值
        int[][] dp = new int[n][c+1];
        // 初始化：背包容量不足w[0]时，价值为0
        for(int j = w[0]; j <= c; j++) {
            dp[0][j] = v[0];
        }

        // 先遍历物品，再遍历容量
        for(int i = 1; i < n; i++) {
            for (int j = 1; j <= c; j++) {
                // 可以放入当前物品
                if (j - w[i] >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                } else { // 不能放入当前物品
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n-1][c];
    }

    /**
     * 0/1背包问题：动态规划解法 - 一维dp数组（滚动数组）- 从后往前遍历
     * @param w
     * @param v
     * @param c
     * @return
     */
    private static int dp_01_rolling_array(int[] w, int[] v, int c) {
        int n = w.length;
        int[] dp = new int[c+1];
        for(int i = 0; i < n; i++) {
            // 容量从后往前遍历，避免使用dp数组前值（同一个背包使用多次， 0/1背包要求只能使用一次）
            for(int j = c; j >= w[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);
            }
        }

        return dp[c];
    }

    /**
     * 暴力解法，回溯算法：选或者不选
     * @param w 物品重量
     * @param v 物品价值
     * @param leftCapacity 背包剩余容量
     * @param idx 当前物品索引
     * @return
     */
    private static int backtrack(int[] w, int[] v, int leftCapacity, int idx) {
        // 递归终止条件
        if (idx == w.length || leftCapacity <= 0) {
            return 0;
        }
        // 不选当前物品
        int exclusive = backtrack(w, v, leftCapacity, idx + 1);
        // 选当前物品
        int inclusive = 0;
        if (w[idx] <= leftCapacity) {
            inclusive = backtrack(w, v, leftCapacity - w[idx], idx + 1) + v[idx];
        }
        // 取最大值
        return Math.max(exclusive, inclusive);
    }
}

5.2 完全背包 Java 实现

package org.stone.study.algo.dp;

/**
 * 完全背包问题
 */
public class Knapsack_Complete_Problem {

    public static void main(String[] args) {
/*        int n = 5, w = 10;
        int[] weights = new int[]{2, 2, 6, 5, 4};
        int[] vals = new int[]{6, 3, 5, 4, 6};*/
        int n = 3, w = 4;
        int[] weights = new int[]{1, 3, 4};
        int[] vals = new int[]{15, 20, 30};
        int ans = complete_bag_02(n, w, weights, vals);
        // 第1组测试数据：30
        // 第2组测试数据：60
        System.out.println("bag total value:" + ans);
    }

    /**
     * 完全背包问题（物品可以使用多次） - 使用暴力解法回溯算法实现
     * @param n
     * @param w
     * @param weights
     * @param vals
     * @return
     */
    public static int complete_bag_01(int n, int w, int[] weights, int[] vals) {
        return backtrack(0, w, weights, vals);
    }

    /**
     * 完全背包问题（物品可以使用多次） - 回溯解法
     * @param i
     * @param w
     * @param weights
     * @param vals
     * @return
     */
    public static int backtrack(int i, int w, int[] weights, int[] vals) {
        if (i == weights.length || w <= 0) {
            return 0;
        }
        // 不选择当前物品
        int maxValue = backtrack(i + 1, w, weights, vals);

        // 选择当前物品: 可多件
        for (int j = 0; j * weights[i] <= w; j++) {
            maxValue = Math.max(maxValue, backtrack(i + 1, w - j * weights[i], weights, vals) + j * vals[i]);
        }

        return maxValue;
    }

    /**
     * 完全背包问题（物品可以使用多次） - 动态规划 2维 数组解法 - 先遍历物品，再遍历重量
     * @param n
     * @param w
     * @param weights
     * @param vals
     * @return
     */
    public static int complete_bag_02(int n, int w, int[] weights, int[] vals) {
        // dp[i][j]表示前i个物品，背包容量为j时的最大价值
        int[][] dp = new int[n][w+1];

        // 先遍历物品，再遍历重量
        for(int i = 0; i < n; i++) {
            for (int j = weights[i]; j <= w; j++) {
                // 不放物品i
                if ( i > 0) {
                    dp[i][j] = dp[i-1][j];
                }

                // 放物品i
                // 注意对于完全背包问题：dp[i][j]是从dp[i][j]和dp[i][j-weights[i]]中推导出来的
                dp[i][j] = Math.max(dp[i][j], dp[i][j - weights[i]] + vals[i]);
            }
        }

        return dp[n-1][w];
    }


    /**
     * 完全背包问题（物品可以使用多次） - 动态规划滚动数组解法 - 先遍历物品，再遍历重量
     * @param n
     * @param w
     * @param weights
     * @param vals
     * @return
     */
    public static int complete_bag_03(int n, int w, int[] weights, int[] vals) {
        // dp[j]表示背包容量为j时的最大价值
        int[] dp = new int[w+1];
        // 先遍历物品，再遍历重量
        for(int i = 0; i < n; i++) {
            // 注意：这里是从小到大遍历。因为物品可以使用多次。dp[j]可以依赖dp[j-weights[i]]
            for (int j = weights[i]; j <= w; j++) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + vals[i]);
            }
        }

        return dp[w];
    }

    /**
     * 完全背包问题（物品可以使用多次） - 动态规划滚动数组解法 - 先遍历重量，再遍历物品
     * @param n
     * @param w
     * @param weights
     * @param vals
     * @return
     */
    private static int complete_bag_04(int n, int w, int[] weights, int[] vals) {
        int[] dp = new int[w + 1];
        // 先遍历重量，再遍历物品
        for (int j = 1; j <= w; j++) {
            for (int i = 0; i < n; i++) {
                if (j - weights[i] >= 0) {
                    dp[j] = Math.max(dp[j], dp[j - weights[i]] + vals[i]);
                }
            }
        }

        return dp[w];
    }
}