• 面试高频手撕算法 - 背包问题2

    目录

    1. 完全背包

    1.1 【模板】完全背包

    1.2 零钱兑换

    1.3 零钱兑换 II

    1.4 完全平方数

    2. 二维费用的背包问题

    2.1 一和零

    2.2 盈利计划

     --- 如果背包问题原先没有基础的，建议先看上一篇博客 --- 面试高频手撕算法 - 01背包系列

    1. 完全背包

    1.1 【模板】完全背包

    【题目链接】

    【模板】完全背包_牛客题霸_牛客网你有一个背包，最多能容纳的体积是V。 现在有n种物品，每种物品有任意多个，第。题目来自【牛客题霸】icon-default.png?t=N7T8https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=230&&tqId=38965&sourceUrl=https%3A%2F%2Fwww.nowcoder.com%2Fexam%2Foj【题目描述】

    1. 你有一个背包，最多能容纳的体积是V。
    2. 现在有 n 种物品，每种物品有任意多个，第 i 种物品的体积为 vi，价值为 wi。
    3.  
    4. （1）求这个背包至多能装多大价值的物品？
    5. （2）若背包恰好装满，求至多能装多大价值的物品？

    第一问：【算法原理】

    再做动态规划系列问题的时候，无非就是这几大步骤：

    ① 状态定义

    ② 推导状态转移方程

    ③ 初始化 dp 表

    ④ 填表顺序

    ⑤

    返回值

    1. 状态定义

    背包问题本质上还是一个线性 dp, 所以状态的定义根据线性 dp 的经验: 

    状态定义: dp[i] 表示从前 i 个物品中挑选, 所有选法, 能挑选出来的最大价值  (试错)

    但是这样定义状态之后, 发现推不出来, 因为不知道体积, 所以需要定义一个二维的 dp.

    状态定义:dp[i][j]表示从前 i 个物品中挑选,总体积不超过 j,所有选法中,能挑选出来的最大价值

    2. 推导状态转移方程 

    根据最后一个位置的状况, 分情况讨论:

            像这种，当我们要表示一个状态的时候，发现它需要很多个状态拼接而成的时候，这个时候我们需要想一个策略，将这些状态用一个或两个等有限个状态来表示。

    【数学思想】

            数学里面有种思想是错位相减，此处的做法有点类似，通过给 dp[i][j] 的列上减去一个体积，得到另一个表达式，然后寻找两个表达式之间的关联关系：

    于是，我们的状态转移方程就转换成了：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - v[i]] + w[i])

    3. 初始化 dp 表

    为了方便代码进行 dp 的一个过程, 我们都会根据情况给 dp 表多加一行, 一列.

    由于使用到前面的列的时候, 会进行判断, 所以初始化的时候, 可以不用初始化列, 只需要初始化行.

    当只有 0 个商品的时候，想要体积不超过 0，1，2，3..... 最大价值肯定都是 0 了.

    4. 填表顺序

    从状态转移方程来分析，dp[i] 会使用到上一行，以及当前行前面的列， 所以填表顺序从上往下，从左往右填.

    5. 返回值

    从状态表示：从前 i 个物品中挑选，总体积不超过 j 的最大价值， 再结合题目要求，

    得出最终的状态：从前 n 个物品中挑选，总体积不超过 V 的最大价值，所以返回 dp[n][V] 即可.

    第一问：【编写关键代码】

    1. /**
    2.  * (1)求这个背包至多能装多大价值的物品？
    3.  * @param v 每个商品所对应的体积
    4.  * @param w 每个商品所对应的价值
    5.  * @param V 背包体积
    6.  * @param n 商品数量
    7.  * @return
    8.  */
    9. public int getMaxVlaue(int[] v, int[] w, int V, int n) {
    10.     int[][] dp = new int[n + 1][V + 1];
    11.     // 从前 i 个商品中挑选,总体积不超过 j,最大价值是多少
    12.     for(int i = 1; i <= n; ++i) {
    13.         for(int j = 1; j <= V; ++j) {
    14.             // 不挑选 i 商品
    15.             dp[i][j] = dp[i - 1][j];
    16.             // 挑选 i 商品, 数学思想简化状态转移方程
    17.             if(j - v[i] >= 0) {
    18.                 dp[i][j] = Math.max(dp[i][j],dp[i][j - v[i]] + w[i]);
    19.             }
    20.         }
    21.     }
    22.     return dp[n][V];
    23. }

    此处先理解最基础的代码，等看完第二问， 再统一做空间优化.

    第二问：【算法原理】

    1. 状态定义

    有了前面的经验，接下来就直接定义状态了.

    状态定义:dp[i][j]表示从前 i 个物品中挑选,总体积正好为 j,所有选法中,能挑选出来的最大价值

    2. 推导状态转移方程

    此处的状态转移方程和第一问几乎一模一样， 只需要处理一些细节：

    根据上面的数学推导，得出的状态转移方程：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - v[i] + w[i]])

            但是此处需要正好装满，所以 j - v[i] 就有可能不存在，所以需要像 01 背包那样，给第一行除第一个位置，全部设为 -1 或者 -0x3f3f3f3f，因为没有商品的时候，不可能凑出体积为 1，2，3 的情况.

    4. 填表顺序

    从上往下，从左往右

    5.返回值

    dp[n][V]

    第二问：【编写关键代码】

    1. /**
    2.  * (2)若背包恰好装满，求至多能装多大价值的物品？
    3.  * @param v 每个商品所对应的体积
    4.  * @param w 每个商品所对应的价值
    5.  * @param V 背包体积
    6.  * @param n 商品数量
    7.  * @return
    8.  */
    9. public static int getMaxVlaue(int[] v, int[] w, int V, int n) {
    10.     int[][] dp = new int[n + 1][V + 1];
    11.     // 状态定义：从前 i 个商品中挑选,体积恰好等于 j,最大价值为多少
    12.  
    13.     // 体积不能正好等于 j 的,统统初始化为 -0x3f3f3f3f
    14.     for(int j = 1; j <= V; ++j) dp[0][j] = -0x3f3f3f3f;
    15.  
    16.     for(int i = 1; i <= n; ++i) {
    17.         for(int j = 1; j <= V; ++j) {
    18.             // 不选 i
    19.             dp[i][j] = dp[i - 1][j];
    20.             // 选 i，-0x3f3f3f3f 不需要做条件判断，因为它足够小，取 max 不影响
    21.             if(j - v[i] >= 0) {
    22.                 dp[i][j] = Math.max(dp[i][j],dp[i][j - v[i]] + w[i]);
    23.             }
    24.         }
    25.     }
    26.     return dp[n][V] < 0 ? 0 : dp[n][V];
    27. }

     【空间优化】

    • 利用滚动数组做空间上的优化
    • 直接在原始代码上稍加修改即可

            利用滚动数组优化的时候，需要注意内层循环的填表顺序，由于 dp[i][j] 只会用到上一行的当前列，以及当前行前面的列，所以内层循环填表和 01 背包不一样，完全背包空间优化后，内层循环需要从左往右填表.

    第一问：空间优化后的代码

    1. /**
    2.  * (1)求这个背包至多能装多大价值的物品？
    3.  * @param v 每个商品所对应的体积
    4.  * @param w 每个商品所对应的价值
    5.  * @param V 背包体积
    6.  * @param n 商品数量
    7.  * @return
    8.  */
    9. public int getMaxVlaue(int[] v, int[] w, int V, int n) {
    10.     int[] dp = new int[V + 1];
    11.     // 从前 i 个商品中挑选,总体积不超过 j,最大价值是多少
    12.     for(int i = 1; i <= n; ++i) {
    13.         for(int j = v[i]; j <= V; ++j) {
    14.             dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
    15.         }
    16.     }
    17.     return dp[V];
    18. }

    第二问：空间优化后的代码

    1. /**
    2.  * (2)若背包恰好装满，求至多能装多大价值的物品？
    3.  * @param v 每个商品所对应的体积
    4.  * @param w 每个商品所对应的价值
    5.  * @param V 背包体积
    6.  * @param n 商品数量
    7.  * @return
    8.  */
    9. public static int getMaxVlaue(int[] v, int[] w, int V, int n) {
    10.     int[] dp = new int[V + 1];
    11.     // 状态定义：从前 i 个商品中挑选,体积恰好等于 j,最大价值为多少
    12.  
    13.     // 体积不能正好凑成 j 的,统统初始化为 -0x3f3f3f3f
    14.     for(int j = 1; j <= V; ++j) dp[j] = -0x3f3f3f3f;
    15.  
    16.     for(int i = 1; i <= n; ++i) {
    17.         for(int j = v[i]; j <= V; ++j) {
    18.             dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
    19.         }
    20.     }
    21.     return dp[V] < 0 ? 0 : dp[V];
    22. }

           有了这两道完全背包的基础之后，后面的完全包相关的题目，可以先自己尝试去做，在看答案之前，自己能做出来，记忆还是非常深刻的.

    1.2 零钱兑换

    【题目链接】

    力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/coin-change/【题目描述】

    1. 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
    2.  
    3. 计算并返回可以凑成总金额所需的最少的硬币个数 。
    4. 如果没有任何一种硬币组合能组成总金额，返回 -1 。
    5.  
    6. 你可以认为每种硬币的数量是无限的。

    示例 1：

    输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

    示例 2：

    输入：coins = [2], amount = 3
输出：-1

    示例 3：

    输入：coins = [1], amount = 0
输出：0

    【算法原理】

    这道题还是很容易能看出来是完全背包问题.

    1. 状态定义

            模仿完全背包的状态定义：dp[i][j] 表示：从前 i 个物品中挑选，总体积不超过 j，所有选法中，最大价值.

    状态定义：dp[i][i] 表示从前 i 个硬币中挑选，总和正好等于 j，所有的选法中，最少的硬币个数

    2. 推导状态转移方程

    根据最后一个位置的状况, 分情况讨论:

            有了上题的经验，当出现这种定义一个状态需要无线个状态来拼接的时候，这个时候我们要想办法把它变成一个或两个状态.

    大家可以自己动手写写递推关系，找到 dp[i][j] 与 dp[i][j - coins[i]] 的关系，得到最终的状态转移方程：dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i] + 1])

    3. 编写代码

    1. /**
    2.  * 零钱兑换 - 完全背包
    3.  * @param coins 硬币数组
    4.  * @param amount 目标值
    5.  * @return
    6.  */
    7. public int coinChange(int[] coins, int amount) {
    8.     int n = coins.length;
    9.     int INF = 0x3f3f3f3f;
    10.     int[][] dp = new int[n + 1][amount + 1];
    11.     // 状态定义：dp[i][i] 表示从前i个硬币中挑选,总和正好等于j,所有的选法中,最少硬币个数
    12.  
    13.     // 不难正好凑成 j 元
    14.     for(int j = 1; j <= amount; ++j) dp[0][j] = INF;
    15.  
    16.     for(int i = 1; i <= n; ++i) {
    17.         for(int j = 0; j <= amount; ++j) {
    18.             // 不选 i
    19.             dp[i][j] = dp[i - 1][j];
    20.             // 选 i, 具体选几个 i,用数学方法优化
    21.             if(j >= coins[i - 1]) {
    22.                 dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
    23.             }
    24.         }
    25.     }
    26.     // 可能不存在正好凑出的情况
    27.     return dp[n][amount] >= INF ? -1 : dp[n][amount];
    28. }

    4. 空间优化

    1. 删掉一维
    2. 内层循环从左往右
    1. /**
    2.  * 零钱兑换 - 完全背包
    3.  * @param coins 硬币数组
    4.  * @param amount 目标值
    5.  * @return
    6.  */
    7. public int coinChange(int[] coins, int amount) {
    8.     int n = coins.length;
    9.     int INF = 0x3f3f3f3f;
    10.     int[] dp = new int[amount + 1];
    11.     // 状态定义：dp[i][i] 表示从前i个硬币中挑选,总和正好等于j,所有的选法中,最少硬币个数
    12.  
    13.     // 不能正好凑成 j 元
    14.     for(int j = 1; j <= amount; ++j) dp[j] = INF;
    15.  
    16.     for(int i = 1; i <= n; ++i) {
    17.         for(int j = coins[i - 1]; j <= amount; ++j) {
    18.             dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
    19.         }
    20.     }
    21.     // 可能不存在正好凑出的情况
    22.     return dp[amount] >= INF ? -1 : dp[amount];
    23. }

    1.3 零钱兑换 II

    【题目链接】

    力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/coin-change-ii/【题目描述】

    1. 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
    2.  
    3. 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
    4.  
    5. 假设每一种面额的硬币有无限个。 
    6.  
    7. 题目数据保证结果符合 32 位带符号整数。

    示例 1：

    输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

    示例 2：

    输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

    示例 3：

    输入：amount = 10, coins = [10] 
输出：1

    【算法原理】

            零钱兑换 II 其实比零钱兑换还简单，此处求的是凑成 j 元的方法数，只要不是求最大价值或最小价值中的正好凑成某某某，初始化工作就很简单.

    1.定义状态

    状态定义：dp[i][i] 表示从前 i 个硬币中挑选，总和正好等于 j，总共有多少种选法

    2. 推导状态转移方程

    有前面的基础了，数学思想直接得出状态转移方程： dp[i][j] = dp[i - 1][j] + dp[i][j- coins[i]]

            此处需要注意的是，第二个状体千万不能在后面 + 1，因为求得是选法，以 i 结尾，是把最后一个位置拼在前面的选法中，所以本质上是同一种选法，求个数才需要 + 1，可以好好体会为什么是这样.

    3. 编写代码 

    1. /**
    2.  * 零钱兑换 II - 完全背包
    3.  * @param coins 硬币数组
    4.  * @param amount 目标值
    5.  * @return
    6.  */
    7. public int change(int amount, int[] coins) {
    8.     int n = coins.length;
    9.     int[][] dp = new int[n + 1][amount + 1];
    10.     // 状态定义：dp[i][i] 表示从前 i 个硬币中挑选，总和正好等于 j，总共有多少种选法
    11.  
    12.     dp[0][0] = 1; // 初始化
    13.  
    14.     for(int i = 1; i <= n; ++i) {
    15.         for(int j = 0; j <= amount; ++j) {
    16.             // 不选 i
    17.             dp[i][j] = dp[i - 1][j];
    18.             if(j >= coins[i - 1]) {
    19.                 // 选 i， 数学思想优化状态转移方程
    20.                 dp[i][j] += dp[i][j - coins[i - 1]];
    21.             }
    22.         }
    23.     }
    24.     return dp[n][amount];
    25. }

    4. 空间优化

    1. 删掉一维
    2. 内层循环从左往右
    1. /**
    2.  * 零钱兑换 II - 完全背包
    3.  * @param coins 硬币数组
    4.  * @param amount 目标值
    5.  * @return
    6.  */
    7. public int change(int amount, int[] coins) {
    8.     int n = coins.length;
    9.     int[] dp = new int[amount + 1];
    10.     // 状态定义：dp[i][i] 表示从前 i 个硬币中挑选，总和正好等于 j，总共有多少种选法
    11.  
    12.     dp[0] = 1; // 初始化
    13.  
    14.     for(int i = 1; i <= n; ++i) {
    15.         for(int j = coins[i - 1]; j <= amount; ++j) {
    16.             dp[j] += dp[j - coins[i - 1]];
    17.         }
    18.     }
    19.     return dp[amount];
    20. }

    1.4 完全平方数

    【题目链接】

    力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/perfect-squares/【题目描述】

    1. 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
    2.  
    3. 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。
    4. 例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

    示例 1：

    输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

    示例 2：

    输入：n = 13
输出：2
解释：13 = 4 + 9

    【算法原理】

            这道题如果想到的是贪心，那么就想错了，对于 13，贪心做法先找 9，再找 4，看似没问题，但是如果是 12，贪心做法先找 9， 再找三个 1，这样就需要 4 个完全平方数了，而三个 4 只需要 3 个完全平方数. 

    所以我们干脆就从第一个开始往后挑，那么就是这样理解：从前 i 个完全平方数中挑选几个数，正好凑成 j，所有的选法中，使用最少的完全平方数.

    这正好就是完全背包问题！

    1.状态定义

    状态定义：从前 i 个完全平方数中挑选，总和正好等于 j，所有的选法中，最小的数量

    2. 推到状态转移方程

     使用数学思想得出最终的状态转移方程：dp[i][j] = Math.min(dp[i - 1][j]，dp[i][j - i * i] + 1)

    3. 编写代码

    1. /**
    2.  * 完全平方数
    3.  * @param n 目标值
    4.  * @return
    5.  */
    6. public int numSquares(int n) {
    7.     int INF = 0x3f3f3f3f;
    8.     // i^2 <= n
    9.     int m = (int)Math.sqrt(n);
    10.     int[][] dp = new int[m + 1][n + 1];
    11.     // 状态定义：从前 i 个完全平方数中挑选，总和正好等于 j，所有的选法中，最小的数量
    12.     for(int j = 1; j <= n; ++j) dp[0][j] = INF; // 不能正好凑成 j
    13.  
    14.     for(int i = 1; i <= m; ++i) {
    15.         for(int j = 1; j <= n; ++j) {
    16.             // 不选 i ^ 2
    17.             dp[i][j] = dp[i - 1][j];
    18.             if(j >= i * i) {
    19.                 // 选 i ^ 2
    20.                 dp[i][j] = Math.min(dp[i][j],dp[i][j - i * i]  + 1);
    21.             }
    22.         }
    23.     }
    24.     return dp[m][n] >= INF ? 0 : dp[m][n];
    25. }

            此处二维 dp 表的横坐标，最多用到 1 ~ 根号 n，因为 13 只会用到 1，4，9，不可能用到 16，所以可以得出 i ^ 2 <= n。

    4. 空间优化

    1. /**
    2.  * 完全平方数
    3.  * @param n 目标值
    4.  * @return
    5.  */
    6. public int numSquares(int n) {
    7.     int INF = 0x3f3f3f3f;
    8.     int m = (int)Math.sqrt(n);
    9.     int[] dp = new int[n + 1];
    10.     // 状态定义：从前 i 个完全平方数中挑选，总和正好等于 j，所有的选法中，最小的数量
    11.     for(int j = 1; j <= n; ++j) dp[j] = INF; // 不能正好凑成 j
    12.  
    13.     for(int i = 1; i <= m; ++i) {
    14.         for(int j = i * i; j <= n; ++j) {
    15.             dp[j] = Math.min(dp[j],dp[j - i * i]  + 1);
    16.         }
    17.     }
    18.     return dp[n] >= INF ? 0 : dp[n];
    19. }

    2. 二维费用的背包问题

            什么是二维费用的背包问题呢，简单来说就是有两个限定条件的背包问题，接下来结合题目来理解二维费用的背包问题.

    2.1 一和零

    【题目链接】

    力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/ones-and-zeroes/【题目描述】

    1. 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
    2.  
    3. 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
    4.  
    5. 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

    示例 1：

    输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

    示例 2：

    输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

    题目意思：从前 i 个字符串中挑选，个数上满足 0 <= 5 && 1 <= n，所有选法中的最大子集.

    【算法原理】

    这题本质上就是二维费用的 01 背包，只不过比 01 背包多一维，做法大致相同.

    1.状态定义

    1. 状态定义：dp[i][j][k] 表示从前 i 个字符串中挑选，字符 0 的个数不超过 j
    2.          字符 1 的个数不超过 k，所有选法中，最大的长度.

    2. 推导状态转移方程

    最终的状态转移方程： dp[i][j][k] = Math.max(dp[i - 1][j][k]，dp[i - 1][j - a][k - b] + 1)

    3. 初始化

    当没有字符串的时候，最大子集长度当然就是 0 了，所以不需要初始化.

    4. 编写代码

    1. /**
    2.  * 一和零 - 二位费用的 01 背包
    3.  * @param strs
    4.  * @param m
    5.  * @param n
    6.  * @return
    7.  */
    8. public int findMaxForm(String[] strs, int m, int n) {
    9.     int L = strs.length;
    10.     int[][][] dp = new int[L + 1][m + 1][n + 1];
    11.     // 从数组中前 i 个字符串中挑选,0的个数不超过 m,
    12.     // 1的个数不超过 n 的所有子集中,长度最大的子集
    13.  
    14.     for(int i = 1; i <= L; ++i) {
    15.         // 计算当前字符串  0,1 的个数
    16.         int a = 0, b = 0;
    17.         for(char ch : strs[i - 1].toCharArray()) {
    18.             if(ch == '0') a++;
    19.             else b++;
    20.         }
    21.         for(int j  = 0; j <= m; ++j) {
    22.             for(int k = 0; k <= n; ++k) {
    23.                 // 不选 i
    24.                 dp[i][j][k] = dp[i -1][j][k];
    25.                 // 选 i
    26.                 if(j >= a && k >= b) {
    27.                     dp[i][j][k] = Math.max(dp[i][j][k], 
    28.                             dp[i - 1][j - a][k - b] + 1);
    29.                 }
    30.             }
    31.         }
    32.     }
    33.     return dp[L][m][n];
    34. }

    5. 空间优化

    1. /**
    2.  * 一和零 - 二位费用的 01 背包
    3.  * @param strs
    4.  * @param m
    5.  * @param n
    6.  * @return
    7.  */
    8. public int findMaxForm(String[] strs, int m, int n) {
    9.     int L = strs.length;
    10.     int[][] dp = new int[m + 1][n + 1];
    11.     // 状态定义：从数组中前 i 个字符串中挑选, 0 的个数不超过 m, 
    12.     // 1 的个数不超过 n 的所有子集中, 长度最大的子集
    13.     for(int i = 1; i <= L; ++i) {
    14.         // 计算当前字符串  0,1 的个数
    15.         int a = 0, b = 0;
    16.         for(char ch : strs[i - 1].toCharArray()) {
    17.             if(ch == '0') a++;
    18.             else b++;
    19.         }
    20.         for(int j = m; j >= a; --j) {
    21.             for(int k = n; k >= b; --k) {
    22.                 dp[j][k] = Math.max(dp[j][k], dp[j - a][k - b] + 1);
    23.             }
    24.         }
    25.     }
    26.     return dp[m][n];
    27. }

    2.2 盈利计划

    【题目链接】

    力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/profitable-schemes/【题目描述】

    1. 集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
    2.  
    3. 第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。
    4. 如果成员参与了其中一项工作，就不能参与另一项工作。
    5.  
    6. 工作的任何至少产生 minProfit 利润的子集称为盈利计划 。并且工作的成员总数最多为 n 。
    7.  
    8. 有多少种计划可以选择？因为答案很大，所以返回结果模 10^9 + 7 的值。

    示例 1：

    输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。

    示例 2：

    输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
输出：7
解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

    题目的意思如下：

     【算法原理】

            这道题与 "一和零" 唯一的区别就是：此处有一个限定条件是满足 >= 某个值，等会需要注意状态转移方程上的差异.

    1. 状态定义

    1. 状态定义：dp[i][j][k] 表示从前 i 个计划中挑选，总人数不超过 j，
    2. 总利润至少为 k，一共有多少种选法

    2. 推导状态转移方程

            此处为什么 k - profit[i] 可以 <0 ？ 因为题目要求的就是利润至少 >= x，如果 profit[i] 已经 > x，那不是更好，并且前面的挑选，我只需要保证利润 >= 0 就可以了.

    所以对于选 i 的这种情况，状态转移方程是需要稍做处理的，因为像 dp[i][j][-3] 这种状态是没有意义的，所以使它利润为 0 即可，也就是 dp[i - 1][j - group[i]][max(0, k - profit(i))]

    所以最终的状态转移方程 : dp[i][j][k] = dp[i - 1][j] + dp[i - 1][j - group[i]][max(0, k - profit(i))]

    3. 编写代码

    1. /**
    2.  * 盈利计划 - 二维费用的背包问题
    3.  * @param n 员工数量
    4.  * @param minProfit 至少产生 minProfit 利润
    5.  * @param group 员工数组
    6.  * @param profit 工作所对应的利润数组
    7.  * @return
    8.  */
    9. public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
    10.     int mod = (int)1e9 + 7;
    11.     int L = group.length;
    12.     int m = minProfit;
    13.     int[][][] dp = new int[L + 1][n + 1][m + 1];
    14.     // 初始化: 任务0, 利润0, 人数 0 <= j <= n, 都有一种选法，所以初始化为 1
    15.     for(int j = 0; j <= n; ++j) dp[0][j][0] = 1;
    16.  
    17.     // 状态：从前 i 个任务中挑选, 人数不超过 j, 利润至少为 k 的选法种数
    18.     for(int i = 1; i <= L; ++i) {
    19.         for(int j = 0; j <= n; ++j) {
    20.             for(int k = 0; k <= m; ++k) {
    21.                 // 不选 i
    22.                 dp[i][j][k] = dp[i - 1][j][k];
    23.                 // 选 i, j - g[i] 必须要 >= 0, 而 k - p[i] 可以小于 0
    24.                 if(j >= group[i - 1]) {
    25.                     dp[i][j][k] += dp[i - 1][j - group[i - 1]][Math.max(0, k - profit[i - 1])];
    26.                 }
    27.                 // 每次让他模上 mod
    28.                 dp[i][j][k] %= mod;
    29.             }
    30.         }
    31.     }
    32.     return dp[L][n][m];
    33. }

    4. 空间优化

    1. /**
    2.  * 盈利计划 - 二维费用的背包问题
    3.  * @param n 员工数量
    4.  * @param minProfit 至少产生 minProfit 利润
    5.  * @param group 员工数组
    6.  * @param profit 工作所对应的利润数组
    7.  * @return
    8.  */
    9. public int profitableSchemes(int n, int minProfit, int[] group, int[] profit){
    10.     int mod = (int)1e9 + 7;
    11.     int L = group.length;
    12.     int m = minProfit;
    13.     int[][] dp = new int[n + 1][m + 1];
    14.     // 初始化: 任务0, 利润0, 人数不超过 j，0 <= j <= n, 都有一种选法，所以初始化为 1
    15.     for(int j = 0; j <= n; ++j) dp[j][0] = 1;
    16.  
    17.     // 状态：从前 i 个任务中挑选, 人数不超过 j, 利润至少为 k 的选法种数
    18.     for(int i = 1; i <= L; ++i) {
    19.         for(int j = n; j >= group[i - 1]; --j) {
    20.             for(int k = m; k >= 0; --k) {
    21.                 dp[j][k] +=
    22.                         dp[j - group[i - 1]][Math.max(0, k - profit[i - 1])];
    23.                 dp[j][k] %= mod;
    24.             }
    25.         }
    26.     }
    27.     return dp[n][m];
    28. }

    【总结 看完背包问题的这两篇文章，之后遇到类似的题目，也能有感觉往背包方面去靠，另外就是要理解背包问题的核心：它是用来解决有限制条件下的 " 组合 " 问题！而有些问题看似也是从一堆物品中挑选，并要求满足某个条件，实则并不是背包问题的，例如这道题：组合总和 IV

            像这种 1，2，1 和 1，1，2 算两种选法的，就不是背包问题，因为这种在数学上称之为排列，而背包问题解决的是组合问题. 

    背包系列讲解到这就结束了，希望能帮助大家.

  • 相关阅读:
    mysql高阶语句
    前端培训丁鹿学堂：vue3中setup语法糖特性写法总结
    ES 查询语法-详解
    AJAX学习（一）
    WindowInsets 分发 & WindowInsets 相关类
    机器学习笔记之卡尔曼滤波(一)动态模型基本介绍
    asp毕业设计——基于C#+asp.net+sqlserver在线英语自学系统设计与实现（毕业论文+程序源码）——在线英语自学系统
    1、认识时间复杂度和简单的排序算法
    线上线下交友社区系统 可打包小程序 支持二开 源码交付！
    在模块中使用外部依赖的类
  • 原文地址：https://blog.csdn.net/xaiobit_hl/article/details/133591843