动态规划：一篇文章带你搞定背包型问题

╰+攻爆jí腚メ 2022-11-09 11:18 248阅读 0赞

入门动态规划请移步动态规划：[基本概念以及面试常见题型][Link 1]

### 一篇文章搞定背包型问题 ###

*   *  什么是背包型动态规划
     *  背包问题分类
     *   *  经典的 01 背包问题
         *  01背包的三种变形
         *  带价值的01背包
         *  01背包的方案数
         *  多重背包
     *  背包问题小结

## 什么是背包型动态规划 ##

*  给出 n 个物品及其大小， 问是否能挑选出一些物品装满大小为 m 的背包
 *  题目中通常有 “和” 以及 “差”的概念，数值会被放到状态中
 *  通常是二维的状态数组， 前 i 个组成和为j状态数组的大小需要开(n+1)\*(m+1)

背包问题: 动规 vs 搜索  
使用组合型深度优先搜索，时间复杂度 O(n \* 2^n) 而动态规划的时间复杂度是 O(n \* m) 动态规划是否一定更好?

> 只有在m>>2^n的时候，动态规划才弱于搜索，所以大部分情况下，动态规划都是一个最优的选择

## 背包问题分类 ##

### 经典的 01 背包问题 ###

> 什么是 01  
> 每个物品要么挑0个(不挑)要么挑1个，所以叫 01。  
> 如果一个物品可以被分割，就不是01背包，如果一个物品可以选多份，就叫多重背包

给出 n 个物品及其大小，问是否能挑选出一些物品装满大小为 m 的背包。

状态表示：

*  状态 state  
    dp\[i\]\[j\] 表示前 i 个物品里挑出若干物品组成和为 j 的大小是否可行  
    两个关键点: 前 & 和
 *  方程 function  
    dp\[i\]\[j\]=dp\[i-1\]\[j\] or dp\[i-1\]\[j-A\[i-1\]\] 如果j>=A\[i-1\]  
    dp\[i\]\[j\]=dp\[i-1\]\[j\]如果 j<A\[i-1\]  
    第i个数的下标是i-1，所以用的是A\[i-1\]而不是A\[i\]
 *  初始化 initialization  
    dp\[0\]\[0\] = true  
    dp\[0\]\[1…m\] = false
 *  答案 answer  
    使得dp\[n\]\[v\], 0s<=v<=m为true的最大v

**例题**

描述：
    在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]
    
    样例
    样例 1:
    	输入:  [3,4,8,5], backpack size=10
    	输出:  9
    
    样例 2:
    	输入:  [2,3,5,7], backpack size=12
    	输出:  12

答案：

public class Solution { 
        /** * @param m: An integer m denotes the size of a backpack * @param A: Given n items with size A[i] * @return: The maximum size */
        public int backPack(int m, int[] A) { 
            // write your code here
            int n = A.length;
            
            //state: dp[i][j] 前 i 个数里能否挑出和为 j
            //前x个数我们的数组长度都需要开 x +1
            boolean[][] dp = new boolean[n + 1][m + 1];
            dp[0][0] = true;
    
            //function
            for(int i = 1; i <= n; i++){ 
                for(int j = 0; j <= m; j++){ 
                    if(j >= A[i - 1]){ 
                        dp[i][j] = dp[i-1][j] || dp[i-1][j-A[i-1]];
                    }else{ 
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }
            //answer
            for(int v = m; v >= 0; v--){ 
                if(dp[n][v]){ 
                    return v;
                }
            }
            return -1;
        }
    }
    
    
    
    //version 2
    //dp[i][j] 表示前 i 个数里挑出若干个数总和 <= j 的最大和是多少
    public int backPack(int m, int[] A) { 
            // write your code here
            if(A == null || A.length == 0){ 
                return 0;
            }
            
            int n = A.length;
            int[][] dp = new int[n + 1][m + 1];
            
            for(int i = 1; i <= n; i++){ 
                for(int j = 0; j <= m; j++){ 
                    if(j >= A[i-1]){ 
                        dp[i][j] = Math.max(
                            dp[i-1][j],
                            dp[i-1][j-A[i-1]] + A[i-1]
                        );
                    }else{ 
                    dp[i][j] = dp[i-1][j];
                    }
                }
            }
        return dp[n][m];
            
        }

**背包问题的重复子问题是什么?**

\[1,2,3,4,5,5,6,7,8,9, 10000\]

比如要凑出和为 10010 前10个数里组合出和为10的方法有5种 这5种组合方式就是重复子问题，因为他们凑出来的和都是10 对于后面 + 10000 之后组成 10010 的影响是一样的 我们不关心 10 是怎么凑的，只关心 10 能不能被凑出来

### 01背包的三种变形 ###

1.最小划分

描述

给出一个正整数数组，写一个程序把这个整数数组分成S1跟S2两部分，使S1中的和跟S2中的和的差的绝对值最小。

> 也就是如果有一个一个整数数组 S 有 n 个数，如果Subset1有 m 个数，Subset2必须有 n-m 个数并且 abs(sum(Subset1) – sum(Subset2)) 应该最小

样例

样例1
    输入: nums = [1, 6, 11, 5]
    输出: 1
    解释: 
    Subset1 = [1, 5, 6]，和是12
    Subset2 = [11]，和是11
    abs(11 - 12) = 1
    
    样例2
    输入: nums = [1, 2, 3, 4]
    输出: 0
    解释: 
    Subset1 = [1, 4], 和是 5
    Subset2 = [2, 3], 和是5   
    abs(5 - 5) = 0

题型变换

设整个数组所有数之和为 SUM, 其中一个较小的数组之和为 X 问题变为求 |SUM - X - X| = |SUM - 2X| 的最小值  
即求使得 X 尽可能接近 SUM/2 的最大值= 数组中挑出若干数尽可能的填满一个大小为 SUM/2 的背包

思路：  
先计算所有数的和，然后取一半halfsum。用boolean\[\] dp来检查array里面取一些数的和能否组成0～halfsum。  
然后从后往前检查dp，遇到的第一个true所代表的i就是array里面取得的数能够组成的最接近总和一半的最大和。

最终两个set的差是sum - 2\*i  
Code

最终两个set的差是sum - 2*i
    public class Solution { 
        public int findMin(int[] arr) { 
            int sum = 0;
            for(int i = 0; i < arr.length; i++){ 
                sum += arr[i];
            }
            boolean[] dp = new boolean[sum / 2 + 1];
            dp[0] = true;
            int min = Integer.MAX_VALUE;
            for(int num : arr){ 
                for(int j = sum / 2; j >= num; j--){ 
                    dp[j] |= dp[j - num];
                }
            }
            
            int i = 0;
            for (i = dp.length - 1; i >= 0; i--) { 
                if (dp[i]) { 
                    break;
                }
            }
            
            return sum - 2 * i;
        }
    }

**2.外卖优惠券**  
你有一张满 X 元减 10 元的满减券和每个菜品的价格(整数)，每 个菜最多只买一份。问最少买多少钱可以用得上这张外卖券?

题型变换：  
挑选若干数之和 >= X 且和最小  
= 挑选出一些“不加入购物车”的菜品 尽可能填满一个 SUM - X 的背包

**3.石头碰撞**  
描述：  
给出 N 个石头及其大小数组 每次选 2 个石头进行碰撞，大小分别为 x,y  
碰撞之后会变成一个石头，大小变为 |x - y| 直到石头个数 < 2为止 问最后剩下来的石头最小是多少?

题型变换：  
本质上这个题的答案=最小划分那一题的答案

### 带价值的01背包 ###

描述  
有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.

问最多能装入背包的总价值是多大?

样例
    样例 1:
    输入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4]
    输出: 9
    解释: 装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9 
    
    样例 2:
    输入: m = 10, A = [2, 3, 8], V = [2, 5, 8]
    输出: 10
    解释: 装入 A[0] 和 A[2] 可以得到最大价值, V[0] + V[2] = 10

public int backPackII(int m, int[] A, int[] V) { 
            // write your code here
            if(A == null || V == null){ 
                return 0;
            }
            
            int n = A.length;
            int[][] dp = new int[n+1][m+1];
            
            for(int i = 1; i <=n; i++){ 
                for(int j = 0; j <= m; j++){ 
                    if(j >= A[i-1]){ 
                        dp[i][j] = Math.max(
                            dp[i-1][j],
                            dp[i-1][j-A[i-1]] + V[i-1]
                        );
                    }else{ 
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }
            return dp[n][m];
        }
    }

### 01背包的方案数 ###

描述：  
给出 n 个物品, 以及一个数组, nums\[i\] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。  
每一个物品只能使用一次

样例
    给出候选物品集合 [1,2,3,3,7] 以及 target 7
    
    结果的集合为:
    [7]
    [1,3,3]

Code:

public int backPackV(int[] nums, int target) { 
    
            // write your code here
            int n = nums.length;
            // 当没有物品时方案数为0
            if (n == 0) { 
                return 0;
            }
            // dp[i][j]表示前i个数字有多少种方式拼出数字j
            int[][] dp = new int[n + 2][target + 2];    
    
            // 初始化dp[i][j]
            for (int i = 0; i <= target; i++) { 
                    dp[0][i] = 0;
            }
    		dp[0][0] = 1;
    		
            for (int i = 1; i <= n; i++) { 
                // 装入的重量
                for (int j = 0; j <= target; j++) { 
                    // 不放物品
                    dp[i][j] = dp[i - 1][j];
                    // 放入物品
                    if (j >= nums[i - 1]) {      
                        dp[i][j] += dp[i - 1][j - nums[i - 1]];
                    }
                }
            }
            return dp[n][target];
        }
    }

### 多重背包 ###

描述：

给定 n 种物品, 每种物品都有无限个. 第 i 个物品的体积为 A\[i\], 价值为 V\[i\]. 再给定一个容量为 m 的背包. 问可以装入背包的最大价值是多少?

样例
    
    样例 1:
    输入: A = [2, 3, 5, 7], V = [1, 5, 2, 4], m = 10
    输出: 15
    解释: 装入三个物品 1 (A[1] = 3, V[1] = 5), 总价值 15.
    
    样例 2:
    输入: A = [1, 2, 3], V = [1, 2, 3], m = 5
    输出: 5
    解释: 策略不唯一. 比如, 装入五个物品 0 (A[0] = 1, V[0] = 1).

用动规四要素分析

*  state: dp\[i\]\[j\] 表示前i个物品挑出一些放到 j 的背包里的最大价值和
 *  function:

dp[i][j] = Math.max(
                            dp[i-1][j],
                            dp[i-1][j-A[i-1]] + V[i-1]
                            dp[i-1][j-A[i-1]*2] + V[i-1]*2
                            ...
                        );
    //其中 0 <= count <= j / A[i - 1]

*  initialization: dp\[0\]\[0…m\] = 0
 *  answer: dp\[n\]\[m\]

优化状态转移方程：

dp[i][j] = Math.max(
                            dp[i-1][j],
                            dp[i-1][j-A[i-1]] + V[i-1]
                            dp[i-1][j-A[i-1]*2] + V[i-1]*2
                            ...
                        );
    //变为
    dp[i][j] = Math.max(
                            dp[i-1][j],
                            dp[i][j-A[i-1]] + V[i-1]
                        );

> 原因：我们可以把dp\[i\]\[j - A\[i - 1\]\]再按照右边的展开，就是dp\[i\]\[j - A\[i - 1\]\] = max(dp\[i - 1\]\[j - A\[i - 1\]\], dp\[i\]\[j - A\[i - 1\] - A\[i - 1\]\] + V\[i - 1\])  
> 那么dp\[i\]\[j\] = max(dp\[i - 1\]\[j\], dp\[i - 1\]\[j - A\[i - 1\]\] + V\[i - 1\], ,  
> dp\[i\]\[j - A\[i - 1\] - A\[i - 1\]\] + V\[i - 1\] + V\[i -> 1\])  
> 如果一直无限展开，就和原来一样了

Code:

public int backPackIII(int m, int[] A, int[] V) { 
            // write your code here
            if(A == null || V == null){ 
                return 0;
            }
            
            int n = A.length;
            int[][] dp = new int[n+1][m+1];
            
            for(int i = 1; i <=n; i++){ 
                for(int j = 0; j <= m; j++){ 
                    if(j >= A[i-1]){ 
                        dp[i][j] = Math.max(
                            dp[i-1][j],
                            dp[i][j-A[i-1]] + V[i-1]
                        );
                    }else{ 
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }
            return dp[n][m];
        }
    }

## 背包问题小结 ##

*  通常是二维的状态数组，前 i 个组成和为 j 状态数组的大小需要开 (n + 1) \* (m + 1)
 *  题目中通常有“和”与“差”的概念，数值会被放到状态中
 *  每个数存在选或者不选两种状态(01背包)
 *  每个数可以选任意多个(多重背包) 数的顺序无关

[Link 1]: https://blog.csdn.net/m0_55221239/article/details/114785883?spm=1001.2014.3001.5501