动态规划——背包问题

叁歲伎倆 2023-06-30 08:58 12阅读 0赞

# 背包问题 #

--------------------

## 目录 ##

1.  概述
2.  背包问题：在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A\[i\]
3.  背包问题：给定N个正整数：A0，A1,…An-1，一个正整数target，求有多少种组合加起来是target
4.  背包问题：给出一个都是正整数的数组 nums，其中没有重复的数。从中找出所有的和为 target 的组合个数
5.  背包问题：有 n 个物品和一个大小为 m 的背包，给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值，问最多能装入背包的总价值是多大?
6.  背包问题：有 n 个物品和一个大小为 m 的背包，给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值，每种物品可以重复，问最多能装入背包的总价值是多大?
7.  小结

--------------------

### 1. 概述 ###

1.  有一个背包，背包有最大承重，商品有若干物品，每个物品有重量和价值
2.  在不撑爆背包的前提下  
    1. 装下最多重量的物品  
    2. 装下最大价值的物品  
    3. 有多少种方式正好带走满满一书包物品
3.  关键点  
    1. 还有几个物品  
    2. 还剩多少承重
4.  入手  
    1. 给定N个物品，重量分别是正整数A0,A1,…An-1  
    2. 每个状物品的方案的总重量都是0到M，对于每个总重量，我们能知道有没有方案能做到，就可以解决

--------------------

### 2. 背包问题：在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A\[i\] ###

##### 1. 题目描述 #####

1.  在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A\[i\]
    
    例子：  
    输入：4个物品，重量为2,3,5,7，背包最大承重是11  
    输出：10（三个物品：2,3,5）

##### 2. 思路 #####

1.  确定状态  
    1. 需要知道N个物品是否能拼出重量W（W=0,1,…M），最后一步：最后一个物品（重量An-1）是否能放入背包  
    2. 情况一：如果前N-1个物品能拼出W，当然前N个物品也能拼出W，如本题，前3个物品能拼出重量8（3+5），自然4个物品也能拼出重量8  
    3. 情况二：如果当前N-1个物品能拼出W-An-1，再加上最后的物品An-1，拼出W。如本题前3个物品能拼出重量2，加上最后一个物品，可以拼出重量9  
    4. 即要求前N个物品能否拼出重量0,1,…M，需要知道前N-1个物品能不能拼出重量0,1,…M
2.  转移方程  
    状态：设f\[i\]\[w\]=能否用前i个物品拼出重量w（true/false）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]
3.  初始条件和边界情况  
    初始条件  
    f\[0\]\[0\]=true:0个物品可以拼出重量0  
    f\[0\]\[1…M\]=false：0个物品不能拼出大于0的重量  
    边界情况  
    f\[i-1\]\[w-Ai-1\]只能在w>Ai-1时使用
4.  计算顺序  
    f\[0\]\[0\],f\[0\]\[1\],…f\[0\]\[M\]  
    计算前一个物品能拼出哪些重量：f\[1\]\[0\],f\[1\]\[1\],…,f\[1\]\[M\]  
    计算前N个物品能拼出哪些重量：f\[N\]\[0\],f\[N\]\[1\],…,f\[N\]\[M\]

##### 3. 代码实现 #####

public static int backPack(int m, int[] A) {
            int n = A.length;
            if (n == 0) {
                return 0;
            }
            //前n个物品能否拼出重量m
            boolean[][] f = new boolean[n + 1][m + 1];
            f[0][0] = true;
            for (int i = 1; i <= m; i++) {
                f[0][i] = false;
            }
    
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= m; j++) {
                    f[i][j] = f[i - 1][j];
                    if (j >= A[i - 1]) {
                        f[i][j] |= f[i - 1][j - A[i - 1]];
                    }
                }
            }
    
            int res = 0;
            for (int i = m; i >= 0; i--) {
        
                if (f[n][i]) {
                    res = i;
                    break;
                }
            }
            return res;
        }

##### 4. 小结 #####

1.  要求不超过target时能拼出的最大重量
2.  记录前i个物品能拼出哪些重量
    
    1.  前 i-1个物品能拼出的重量
    2.  前 i-1个物品能拼出的重量 + 第 i 个物品重量 Ai-1

--------------------

### 3. 背包问题：给定N个正整数：A0，A1,…An-1，一个正整数target，求有多少种组合加起来是target ###

##### 1. 题目描述 #####

1.  给定N个正整数：A0，A1,…An-1，一个正整数target，求有多少种组合加起来是target
    
    例子：  
    输入：A=\[1,2,3,3,7\]，target=7  
    输出：2（7=7，1+3+3=7）

##### 2. 思路 #####

1.  确定状态  
    1. 需要知道N个物品有多少种方式拼出重量W(W=0,1…,target)  
    最后一步：第N个物品(重量An-1)是否进入背包  
    2. 情况一：如果前N-1个物品能拼出W  
    3. 情况二：如果当前N-1个物品能拼出W-An-1，再加上最后的物品An-1，拼出W  
    4. 情况一和情况二的个数=用N个物品拼出W的方式
2.  转移方程  
    状态：设f\[i\]\[w\]=用前i个物品有多少种方式拼出重量w  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]
3.  初始条件和边界情况  
    初始条件  
    f\[0\]\[0\]=1:0个物品有1种方式可以拼出重量0  
    f\[0\]\[1…M\]=0：0个物品不能拼出大于0的重量  
    边界情况  
    f\[i-1\]\[w-Ai-1\]只能在w>Ai-1时使用
4.  计算顺序  
    f\[0\]\[0\],f\[0\]\[1\],…f\[0\]\[M\]  
    计算前一个物品有多少种方式能拼出哪些重量：f\[1\]\[0\],f\[1\]\[1\],…,f\[1\]\[M\]  
    …  
    计算前N个物品有多少种方式能拼出哪些重量：f\[N\]\[0\],f\[N\]\[1\],…,f\[N\]\[M\]

##### 3. 代码实现 #####

public static int backPackV(int[] A, int m) {
            int n = A.length;
            if (n == 0) {
                return 0;
            }
            int[][] f = new int[n + 1][m + 1];
            f[0][0] = 1;
            for (int i = 1; i <= m; i++) {
                f[0][i] = 0;
            }
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= m; j++) {
                    f[i][j] = f[i - 1][j];
                    if (j >= A[i - 1]) {
                        f[i][j] += f[i - 1][j - A[i - 1]];
                    }
                }
            }
            return f[n][m];
        }
    
        public static int backPackV2(int[] A, int m) {
            int n = A.length;
            int[] f = new int[m + 1];
            f[0] = 1;
            for (int i = 1; i <= m; i++) {
                f[i] = 0;
            }
            for (int i = 1; i <= n; i++) {
                for (int j = m; j >= 0; j--) {
        
                    if (j >= A[i - 1]) {
                        f[j] += f[j - A[i - 1]];
                    }
                }
            }
            return f[m];
        }

--------------------

### 4. 背包问题：给出一个都是正整数的数组 nums，其中没有重复的数。从中找出所有的和为 target 的组合个数 ###

##### 1. 题目描述 #####

1.  给出一个都是正整数的数组 nums，其中没有重复的数。从中找出所有的和为 target 的组合个数
    
    例子：  
    输入：A=\[1,2,4\]，target=4  
    输出：6（\[1,1,1,1\],\[1,1,2\],\[1,2,1\],\[2,1,1\],\[2,2\],\[4\]）

##### 2. 思路 #####

1.  确定状态  
    1. 关注最后一步：最后一个物品的重量是多少  
    2. 任何一个正确的组合中，所有物品总重量是target  
    3. 如果最后一个物品重量是K，则前面的物品重量是target-K  
    4. 如果最后一个物品重量是A0，则要求多少种组合能拼出target-A0  
    …  
    5. 如果最后一个物品重量是An-1，则要求多少种组合能拼出target-An-1
2.  转移方程  
    状态：设f\[i\] = 有多少种组合能拼出重量 i  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]
3.  初始条件和边界情况  
    1. 初始条件  
    f\[0\] = 1：有一种组合能拼出重量0  
    2. 边界情况  
    如果i<Aj，则对应的 f\[i-Aj\]不能加入 f\[i\]
4.  计算顺序  
    f\[0\],f\[1\],…f\[target\]

##### 3. 代码实现 #####

public static int backPackVI(int[] A, int m) {
            int[] f = new int[m + 1];
            f[0] = 1;
            for (int i = 1; i <= m; i++) {
                f[i] = 0;
                for (int j = 0; j < A.length; j++) {
                    if (i >= A[j]) {
                        f[i] += f[i - A[j]];
                    }
                }
            }
            return f[m];
        }

--------------------

### 5. 背包问题：有 n 个物品和一个大小为 m 的背包，给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.问最多能装入背包的总价值是多大? ###

##### 1. 题目描述 #####

1.  有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.
2.  问最多能装入背包的总价值是多大?
    
    例子：  
    输入：4个物品，重量为2,3,5,7，价值为1,5,2,4，背包最大承重是11  
    输出：9（物品1+物品3，重量3+7=10，价值5+4=9）

##### 2. 思路 #####

1.  确定状态  
    1. 对于每个总重量，我们能知道对应的最大价值是多少，就能求出答案  
    2. 最后一步：第N个物品(重量An-1，价值Vn-1)是否进入背包  
    3. 情况一：如果前N-1个物品能拼出W，最大价值是V，前N个物品也能拼出W并且总价值是V  
    4. 情况二：如果当前N-1个物品能拼出W-An-1，最大总价值V，则再加上最后的物品（重量An-1，价值Vn-1），拼出W，总价值V+Vn-1  
    5. 情况一和情况二的最大值=用N个物品拼出重量W时的最大总价值
2.  转移方程  
    状态：设f\[i\]\[w\]=用前i个物品有拼出重量w时最大总价值（-1表示不能拼出W）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 3]
3.  初始条件和边界情况  
    初始条件  
    f\[0\]\[0\]=1:0个物品可以拼出重量0，最大总价值是0  
    f\[0\]\[1…M\]=0：0个物品不能拼出大于0的重量，最大总价值-1  
    边界情况  
    f\[i-1\]\[w-Ai-1\]只能在w>Ai-1时使用，并且f\[i-1\]\[w-Ai-1\] != -1时使用
4.  计算顺序  
    f\[0\]\[0\],f\[0\]\[1\],…f\[0\]\[M\]  
    计算前一个物品拼出各种重量的最大价值：f\[1\]\[0\],f\[1\]\[1\],…,f\[1\]\[M\]  
    …  
    计算前一个物品拼出各种重量的最大价值：f\[N\]\[0\],f\[N\]\[1\],…,f\[N\]\[M\]

##### 3. 代码实现 #####

public static int backPackII(int m, int[] A, int[] V) {
            int n = A.length;
            if (n == 0) {
                return 0;
            }
            int[][] f = new int[n + 1][m + 1];
            f[0][0] = 0;
            for (int i = 1; i <= m; i++) {
                f[0][i] = -1;
            }
    
            for (int i = 1; i <= n; i++) {
                for (int w = 0; w <= m; w++) {
                    f[i][w] = f[i - 1][w];
                    if (w >= A[i - 1] && f[i - 1][w - A[i - 1]] != -1) {
                        f[i][w] = Math.max(f[i][w], f[i - 1][w - A[i - 1]] + V[i - 1]);
                    }
                }
            }
    
            int res = 0;
            for (int w = 0; w <= m; w++) {
                if (f[n][w] != -1) {
                    res = Math.max(res, f[n][w]);
                }
            }
            return res;
        }

--------------------

### 6. 背包问题：有 n 个物品和一个大小为 m 的背包，给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值，每种物品可以重复，问最多能装入背包的总价值是多大? ###

##### 1. 题目描述 #####

1. 有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.
    2. 每种物品都有无穷多个，问最多能装入背包的总价值是多大?
    例子：

输入：4个物品，重量为2,3,5,7，价值为1,5,2,4，背包最大承重是11  
输出：15（3个物品1，重量3*3=9，价值5*3=15）

##### 2. 思路 #####

1.  确定状态  
    1. 对于每个总重量，我们能知道对应的最大价值是多少，就能求出答案  
    2. 最后一步：第N种物品(重量An-1，价值Vn-1)是否进入背包  
    3. 情况一：如果前N-1种物品能拼出W，最大价值是V，前N个物品也能拼出W并且总价值是V  
    4. 情况二：如果当前N-1种物品能拼出W-An-1，最大总价值V，则再加上最后的物品（重量An-1，价值Vn-1），拼出W，总价值V+Vn-1  
    5. 情况一和情况二的最大值=用N种物品拼出重量W时的最大总价值
2.  转移方程  
    状态：设f\[i\]\[w\]=用前i种物品有拼出重量w时最大总价值（-1表示不能拼出W）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 4]  
    优化后![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 5]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 6]
3.  初始条件和边界情况  
    初始条件  
    f\[0\]\[0\]=1:0种物品可以拼出重量0，最大总价值是0  
    f\[0\]\[1…M\]=0：0种物品不能拼出大于0的重量，最大总价值-1  
    边界情况  
    f\[i-1\]\[w-Ai-1\]只能在w>Ai-1时使用，并且f\[i-1\]\[w-Ai-1\] != -1时使用
4.  计算顺序  
    f\[0\]\[0\],f\[0\]\[1\],…f\[0\]\[M\]  
    计算前一种物品拼出各种重量的最大价值：f\[1\]\[0\],f\[1\]\[1\],…,f\[1\]\[M\]  
    …  
    计算前N种物品拼出各种重量的最大价值：f\[N\]\[0\],f\[N\]\[1\],…,f\[N\]\[M\]

##### 3. 代码实现 #####

public static int backPackIII(int m, int[] A, int[] V) {
            int n = A.length;
            if (n == 0) {
                return 0;
            }
            int[][] f = new int[n + 1][m + 1];
            f[0][0] = 0;
            for (int i = 1; i <= m; i++) {
                f[0][i] = -1;
            }
    
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= m; j++) {
                    f[i][j] = f[i - 1][j];
                    if (j >= A[i - 1] && f[i][j - A[i - 1]] != -1) {
                        f[i][j] = Math.max(f[i][j], f[i][j - A[i - 1]] + V[i - 1]);
                    }
                }
            }
    
            int res = 0;
            for (int i = 0; i <= m; i++) {
                if (f[n][i] != -1) {
                    res = Math.max(res, f[n][i]);
                }
            }
            return res;
        }

--------------------

### 7. 小结 ###

1.  可行性背包  
    1. 题面  
    要求不超过target时能拼出的最大重量  
    2. 记录f\[i\]\[w\] = 前 i 个物品能不能拼出重量 w
2.  计数型背包  
    1. 题面  
    要求有多少种方式拼出重量target  
    2. 记录 f\[i\]\[w\] = 前 i 个物品有多少种方式拼出重量 w
3.  最值型背包  
    1. 题面  
    要求能拼出的最大价值  
    2. 记录 f\[i\]\[w\] = 前 i 个/种物品拼出重量 w 能得到的最大价值
4.  关键点  
    1. 最后一步  
    1. 最后一个背包内的物品是哪个  
    2. 最后一个物品有没有进背包  
    2. 数组大小和最大承重target有关

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200116134801480.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200118154749593.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200118154713719.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200118154619126.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200118161227907.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200118161259973.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200118161232812.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70