0-1 背包问题

梦里梦外; 2022-11-27 07:10 115阅读 0赞

# 0-1 背包问题 #

## 1、参考资料 ##

https://www.cnblogs.com/ClearMoonlight/p/10456648.html

https://www.cnblogs.com/aiguona/p/7274222.html

## 2、问题描述 ##

给定n个物品，每个物品有一个重量（也可以看作体积）`weight[i]`和一个价值`value[i]`，其中i的范围`1≤i≤n`，现有一个给定容量m的背包，求解背包里装入的物品价值之和的最大值。

## 3、问题分析 ##

> **动态规划原理**

动态规划是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。

动态规划则通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取（子问题的最优解），避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

> **动态规划过程**

1.  用v\[i\]表示物品价值，w\[i\]表示物品重量。定义状态`dp[i][j]`以j为容量为放入前i个物品(按i从小到大的顺序)的最大价值。
2.  初始化边界条件，`dp[0][j]=dp[i][0]=0`；
3.  对于每一个物品，有两种选择方法，能装下和不能装下：
    
     *  第一，包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即`dp[i][j]=dp[i-1][j]`；
     *  第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即`dp[i][j]=max(dp[i-1][j], dp[i-1][j-wt[i]]+val[i])`，其中`dp[i-1][j]`表示不装第 i 件物品，`dp[i-1][j-wt[i]]+val[i]`表示装了第i个商品，背包容量减少`wt[i]`，但价值增加了`val[i]`；
4.  得出递推关系式：
    
     *  若`j<w[i]`，则`dp[i][j]=dp[i-1][j]`
     *  若`j>=w[i]`，则`dp[i][j]=max(dp[i-1][j]，dp[i-1][j-wt[i]]+val[i])`

![image-20200814100414882][]

> **动态规划表格**

*  eg：物品数量为 4，背包容量为 8

*  初始状态将边界初始化为0。j表示背包的的重量，i表示第i个物品，填表方式为一行一行的填，每次填写的时候取 `dp[i-1,j]`，`dp[i-1,j-wt[i]]+val[i]`中的较大值

## 4、代码实现 ##

*  代码

/**
     * @ClassName KnapsackDemo
     * @Description TODO
     * @Author Heygo
     * @Date 2020/8/2 10:23
     * @Version 1.0
     */
    public class KnapsackDemo {
        
    
        public static void main(String[] args) {
        
    
            int maxValue = knapsack(8, 4, new int[]{
        -1, 2, 3, 4, 5}, new int[]{
        -1, 3, 4, 5, 6});
            System.out.println(maxValue);
    
        }
    
        /**
         * 0-1 背包问题
         *
         * @param W   背包的重量
         * @param N   现有物品的数量
         * @param wt  物品的重量
         * @param val 物品的价值
         * @return 背包中物品的最大价值
         */
        public static int knapsack(int W, int N, int[] wt, int[] val) {
        
    
            // dp[i][w] 表示：对于前 i 个物品，当背包容量为 w 时，能放下的最大价值为 dp[i][w]
            int[][] dp = new int[N + 1][W + 1];
    
            // 从第一个物品开始，一个一个放入物品
            for (int i = 1; i <= N; i++) {
        
                // 背包重量逐渐增大，尝试放入物品
                for (int w = 1; w <= W; w++) {
        
                    // dp[][] 数组中的 i 对应 wt[] 和 val[] 数组中的 i
                    if (w - wt[i] < 0) {
        
                        // 当前背包容量装不下，只能选择不装入背包，选择上一次的最大价值作为这次的最大价值
                        dp[i][w] = dp[i - 1][w];
                    } else {
        
                        /*
                        当前背包容量能装下：
                            w - wt[i] ：装入当前物品，背包还剩余多少空间（重量）
                            dp[i - 1][w - wt[i]] ：重量为 w - wt[i] 的背包最多能装下多大价值的物品
                            val[i] ：当前物品的价值
                            (dp[i - 1][w - wt[i]] + val[i]) ：装下当前物品后，背包中物品的最大价值
                            dp[i - 1][w] ：上一次的最大价值
                        尝试着将当前物品放入背包，和上一次的价值比，看看谁大谁小，选价值大的
                         */
                        dp[i][w] = Math.max((dp[i - 1][w - wt[i]] + val[i]), dp[i - 1][w]);
                    }
                }
            }
    
            for (int[] ints : dp) {
        
                System.out.println(Arrays.toString(ints));
            }
    
            return dp[N][W];
        }
    
    }

*  程序运行结果

[0, 0, 0, 0, 0, 0, 0, 0, 0]
    [0, 0, 3, 3, 3, 3, 3, 3, 3]
    [0, 0, 3, 4, 4, 7, 7, 7, 7]
    [0, 0, 3, 4, 5, 7, 8, 9, 9]
    [0, 0, 3, 4, 5, 7, 8, 9, 10]
    10

## 5、代码优化 ##

> **代码的空间优化**

1.  由上面的图可以看出来，每一次`dp[i][j]`改变的值只与`dp[i-1][x]`有关，其中 `1<=x<j`，`dp[i-1][x]`是放入第 i 件物品，背包容量为 x 对应的最优解
2.  因此，可以将`dp[][]`缩减成一维数组`dp[]`，从而达到优化空间的目的，此时的状态转移方程转换为`dp[j]=max(dp[j], dp[j-wt[i]]+val[i])`
3.  由于状态转移方程每一次推导`dp[j]`是通过`dp[x]`来推导的，其中`1<=x<j`，所以一维数组中 j 的扫描顺序应该从大到小，即从capacity到1，否者上一步的最优解的值将会被修改，从而造成错误

![image-20200814100431887][]

> **代码实现**

*  代码

/**
     * @ClassName KnapsackOptimizationDemo
     * @Description TODO
     * @Author Heygo
     * @Date 2020/8/10 21:58
     * @Version 1.0
     */
    public class KnapsackOptimizationDemo {
        
    
        public static void main(String[] args) {
        
    
            int maxValue = knapsack(8, 4, new int[]{
        -1, 2, 3, 4, 5}, new int[]{
        -1, 3, 4, 5, 6});
            System.out.println(maxValue);
    
        }
    
        /**
         * 0-1 背包问题
         *
         * @param W   背包的重量
         * @param N   现有物品的数量
         * @param wt  物品的重量
         * @param val 物品的价值
         * @return 背包中物品的最大价值
         */
        public static int knapsack(int W, int N, int[] wt, int[] val) {
        
    
            // dp[w] 表示：对于前 i(数组下标) 个物品，当背包容量为 w 时，能放下的最大价值为 dp[w]
            int[] dp = new int[W + 1];
    
            // 从第一个物品开始，一个一个放入物品
            for (int i = 1; i <= N; i++) {
        
                /*
                    由于使用了一维数组，如果还是升序遍历的话，当前步骤的最优解会覆盖上一步骤的最优解，所以需要降序遍历
                    w = W ：从背包最大容量开始降序
                    w >= wt[i] ：如果背包装不下此物品，则沿用上次的最优解
                 */
                for (int w = W; w >= wt[i]; w--) {
        
                    dp[w] = Math.max(dp[w - wt[i]] + val[i], dp[w]);
                }
                System.out.println(Arrays.toString(dp));
            }
    
            return dp[W];
        }
    }

*  程序运行结果

[0, 0, 3, 3, 3, 3, 3, 3, 3]
    [0, 0, 3, 4, 4, 7, 7, 7, 7]
    [0, 0, 3, 4, 5, 7, 8, 9, 9]
    [0, 0, 3, 4, 5, 7, 8, 9, 10]
    10

[image-20200814100414882]: /images/20221124/5b8fadefa6e64c1798ad3c208a077584.png
[image-20200814100431887]: /images/20221124/5a0dad3527914fe59740b428bc4dcc3c.png