【动态规划篇】：解析背包问题--动态规划塑造的算法利器

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：动态规划篇–CSDN博客

一.01背包问题

动态规划中的01背包问题其目标是在给定背包容量的情况下，选择物品以最大化总价值，其中每个物品个数有限制，只有一个，因此只能选或者不选两种情况，这里通过一道模板题来讲解：

1.模板题

题目：

算法原理：

如图所示：

代码实现：

const int N = 1001;
//全局变量，默认值为0
int n, V, dp[N][N], v[N], w[N];int main(){//输入物品个数和背包容量cin >> n >> V;//输入每个物品的体积和价值for (int i = 1; i <= n; i++){cin >> v[i] >> w[i];}//问题一状态表示 dp[i][j]表示挑选前i个物品，体积不超过j的最大价值//初始值全部设置为0for (int i = 1; i <= n; i++){for (int j = 1; j <= V; j++){//如果不挑选当前i物品，找挑选前i-1个物品不超过j的最大价值dp[i][j] = dp[i - 1][j];//如果挑选当前i物品,找挑选前i-1个物品不超过j-v[i]的最大价值然后加上当前物品的价值//两种情况取最大值if (j >= v[i]){dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i][j]);}}}//输出结果cout << dp[n][V] << endl;//初始化状态表memset(dp, 0, sizeof dp);//问题二状态表示 dp[i][j]表示挑选前i个物品，提及恰好等于j的最大价值//第一行除第一个外，其他全初始值设置为-1for (int j = 1; j <= V; j++){dp[0][j] = -1;}//填表for (int i = 1; i <= n; i++){for (int j = 1; j <= V; j++){//如果不挑选当前i物品，找挑选前i-1个物品,体积恰好等于j的最大价值dp[i][j] = dp[i - 1][j];//如果挑选当前i物品，找挑选前i-1个物品，体积恰好等于j-v[i]的最大价值if (j >= v[i] && dp[i - 1][j - v[i]] != -1){dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i][j]);}}}//输出结果cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;return 0;
}

空间优化：

将原本的二位状态表优化为一维状态表，每行都在上一行的对应下标的位置上更新，注意填表顺序必须是每行从右往左。

const int N = 1001;
//全局变量，默认值为0
int n, V, dp[N], v[N], w[N];
int main(){//输入物品个数和背包体积cin >> n >> V;//输入每个物品的体积和价值for (int i = 1; i <= n; i++){cin >> v[i] >> w[i];}//问题一for (int i = 1; i <= n; i++){for (int j = V; j >= v[i]; j--){dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}//输出结果cout << dp[V] << endl;//初始化状态表memset(dp, 0, sizeof dp);//问题二for (int j = 1; j <= V; j++){dp[j] = -1;}for (int i = 1; i <= n; i++){for (int j = V; j >= v[i]; j--){if (dp[j - v[i]] != -1){dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}}//输出结果cout << (dp[V] == -1 ? 0 : dp[V]) << endl;return 0;
}

2.例题

1.分割等和子集

题目：

算法原理：

根据题意，将数组分割成两个相等的子集，因此需要先求出整个数组的总和sum，然后除以2，就是每个子集的总和，然后从原数组中挑选元素使其总和为sum/2，如果能找到就表示能分割成两个相等的子集，如果不能找到就表示不能分割。因此就转换成01背包问题中的问题二，挑选物品使其恰好装满背包。

状态表示： dp[i][j]表示挑选前i个数，所有的选法中，能否恰好等于j。

状态转移方程：根据当前位置元素nums[i-1]（下表映射需要减一）选或者不选分为两种情况，选：dp[i-1][j]；不选：dp[i-1][j-nums[i-1]]（前提条件：j>=nums[i-1]）；两种情况满足其中一种即可。

初始化：添加第0行和第0列,除第一行外其余全部为true。

填表顺序：从第一行到最后一行，其中每一行从左往右。

返回值：dp[n][sum]，从前n个数中挑选，所有的选法中能否恰好等于sum。

代码实现：

bool canPartition(vector<int>& nums){int sum=0;for(auto num : nums){sum += num;}if (sum % 2 == 1){return false;}sum /= 2;int n = nums.size();//状态表示 dp[i][j]表示挑选前i个数，所有的选法中，能否恰好等于jvector<vector<bool>> dp(n + 1, vector<bool>(sum + 1,true));//初始化 添加第0行和第0列,除第一行外其余全部为truefor (int j = 1; j <= sum; j++){dp[0][j] = false;}//填表for (int i = 1; i <= n; i++){for (int j = 1; j <= sum; j++){//当前位置i元素要么选要么不选，两种情况满足一种即可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][sum];
}

空间优化：

bool canPartition(vector<int>& nums){int n = nums.size();int sum = 0;for(auto num : nums){sum += num;}if (sum % 2 == 1){return false;}sum /= 2;//状态表示vector<bool> dp(sum + 1);//初始化dp[0] = true;//填表for (int i = 1; i <= n; i++){for (int j = sum; j >= nums[i - 1]; j--){if (dp[j - nums[i - 1]] != false){dp[j] = dp[j] || dp[j - nums[i - 1]];}}}//返回值return dp[sum];
}

2.目标和

题目：

算法原理：

根据题意在原数组中每个元素前添加正好或者负号，相当于将原数组分成两堆，一堆为正数，一堆为负数，假设正数的和为a，负数的和的绝对值为b，原数组的和为sum，a-b=target && a+b=sum => a=(sum+target)/2，因此转化成从原数组中挑选几个数和为a，总共有多少种选法。

状态表示： dp[i][j]表示从前i个数中挑选，和恰好为j，总共有多少种选法。

初始化： dp[0][0]表示从前0个数中挑选，和恰好为0，有1种选法，第0行表示从前0个数中挑选，和恰好为j(j>=1)，有0种选法。

状态转移方程：根据当前位置元素nums[i-1]（下表映射需要减一）选或者不选分为两种情况，选：dp[i-1][j]；不选：dp[i-1][j-nums[i-1]]（前提条件：j>=nums[i-1]）；因为要统计所有选法，所以两种情况选法个数相加。

填表顺序：从第一行到最后一行，其中每一行从左往右。

返回值：dp[n][a]，从前n个数中挑选，和恰好为a，总共有多少种选法。

代码实现：

int findTargetSumWays(vector<int>& nums, int target){int n = nums.size();int sum = 0;for(auto num : nums){sum += num;}if (sum + target < 0 || (sum + target) % 2 == 1){return 0;}int a = (sum + target) / 2;//状态表示 dp[i][j]表示从前i个数中挑选，和恰好为j，总共有多少种选法vector<vector<int>> dp(n + 1, vector<int>(a + 1));//初始化 dp[0][0]表示从前0个数中挑选，和恰好为0，有1种选法//第0行表示从前0个数中挑选，和恰好为j(j>=1)，有0种选法dp[0][0] = 1;//填表for (int i = 1; i <= n; i++){for (int j = 0; j <= a; 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][a];
}

空间优化：

int findTargetSumWays(vector<int>& nums, int target){int n = nums.size();int sum = 0;for(auto num :nums){sum += num;}if (sum + target < 0 || (sum + target) % 2 == 1){return 0;}int a = (sum + target) / 2;//状态表示vector<int> dp(a + 1);//初始化dp[0] = 1;//填表for (int i = 1; i <= n; i++){for (int j = a; j >= nums[i - 1]; j--){//状态转移方程dp[j] += dp[j - nums[i - 1]];}}//返回值return dp[a];
}

3.最后一块石头的重量

题目：

算法原理：

根据题意要求，假设现在有一堆石头[a,b,c,d,e]，先挑选b和c两个石头，剩余[a,b-c,d,e]，然后挑选d和e两个石头，剩余[a,b-c,d-e]，然后挑选a和b-c两个石头，剩余[a-b+c,d-e]，最后两个石头相减，剩余[a-b+c-d+e]，最后剩余石头的质量就是每个石头的质量相加减，其实和上一题有点相似，最后这个表达式就是在每个数字前添加正号和负号，然后分成两堆，一堆为正数，一堆为负数。

假设所有正数的总和为a，所有负数的总和绝对值为b，所有数的和为a+b=sum，要使a-b的绝对值最小，只需a和b两个值无限接近总和sum的一半即可，这样两个数相减一定是最小的，因此本道题就是转换成从所有石头中挑选，使其总和不超过aim=sum/2的最大重量。

状态表示： dp[i][j]表示挑选前i个石头，使重量和接近j所有选法种，最大的重量。

初始化 ：dp[0][0]表示挑选前0个石头，使重量和接近0的最大重量，就是0，第0行表示挑选前0个石头，使重量和接近j(j>=1)的最大重量，就是0，第0列表示挑选前i(i>=1)个石头,使重量和接近0的最大重量，还是0。

状态转移方程：根据当前石头选还是不选分情况讨论，选：dp[i-1][j]；不选：dp[i-1][j-stones[i-1]]（前提条件：j>=stones[i-1]）；因为要统计最大值，所以两种情况取最大值。

返回值：因为找到当前一堆的石头重量为dp[n][aim]，另一堆石头重量就是sum-dp[n][aim]，根据上面的表达式，最后两堆石头相减就是最小值，因此返回结果就是sum - 2 * dp[n][aim]。

代码实现：

int lastStoneWeightII(vector<int>& stones){int n = stones.size();int sum = 0;for(auto num : stones){sum += num;}int aim = sum / 2;//状态表示 dp[i][j]表示挑选前i个石头，使重量和接近j所有选法种，最大的重量vector<vector<int>> dp(n + 1, vector<int>(aim + 1));//初始化 dp[0][0]表示挑选前0个石头，使重量和接近0的最大重量，就是0//第0行表示挑选前0个石头，使重量和接近j(j>=1)的最大重量，就是0//第0列表示挑选前i(i>=1)个石头,使重量和接近0的最大重量，还是0//填表for (int i = 1; i <= n; i++){for (int j = 1; j <= aim; j++){//不挑选当前i石头dp[i][j] = dp[i - 1][j];//挑选当前i石头if (j >= stones[i - 1]){dp[i][j] = max(dp[i - 1][j - stones[i - 1]] + stones[i - 1], dp[i][j]);}}}//返回值return sum - 2 * dp[n][aim];
}

空间优化：

int lastStoneWeightII(vector<int>& stones){int n = stones.size();int sum = 0;for(auto num : stones){sum += num;}int aim = sum / 2;//状态表示vector<int> dp(aim + 1);//填表for (int i = 1; i <= n; i++){for (int j = aim; j >= stones[i - 1]; j--){//状态转移方程dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);}}//返回值return sum - 2 * dp[aim];
}

二.完全背包问题

动态规划中的完全背包问题其目标是在给定背包容量的情况下，选择物品以最大化总价值，而每个物品个数不限制，可以选0个，1个，2个等等多种情况，这里通过一道模板题来讲解：

1.模板题

题目：

算法原理：

如图所示：

代码实现：

const int N = 1001;
int n, V, v[N], w[N];
int dp[N][N];int main(){//输入物品个数和背包体积cin >> n >> V;//输入每个物品的体积和价值for (int i = 1; i <= n; i++){cin >> v[i] >> w[i];}//问题一状态表示 dp[i][j]表示挑选前i个物品，背包体积不超过j的所有选法中，最大的价值//填表for (int i = 1; i <= n; i++){for (int j = 0; j <= V; j++){dp[i][j] = dp[i - 1][j];if (j >= v[i]){dp[i][j] = max(dp[i][j - v[i]] + w[i], dp[i][j]);}}}//输出结果cout << dp[n][V] << endl;//初始化状态表memset(dp, 0, sizeof dp);//问题二状态表示 dp[i][j]表示挑选前i个物品，背包体积恰好等于j的所有选法中，最大的价值//先初始化第一行为-1，表示不存在的情况for (int j = 1; j <= V; j++){dp[0][j] = -1;}//填表for (int i = 1; i <= n; i++){for (int j = 0; j <= V; j++){dp[i][j] = dp[i - 1][j];if (j >= v[i] && dp[i][j - v[i]] != -1){dp[i][j] = max(dp[i][j - v[i]] + w[i], dp[i][j]);}}}//输出结果cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;return 0;
}

空间优化：

将原本的二维状态表优化为一维状态表，每行的状态值都在上一行对应的位置上填写，注意填写顺序每行必须是从左往右填写。

int dp[N];
int main(){//输入物品个数和背包体积cin >> n >> V;//输入每个物品的体积和价值for (int i = 1; i <= n; i++){cin >> v[i] >> w[i];}//问题一状态表示 dp[i][j]表示挑选前i个物品，背包体积不超过j的所有选法中，最大的价值//填表for (int i = 1; i <= n; i++){//和01背包不同的是从左往右填for (int j = v[i]; j <= V; j++){dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}//输出结果cout << dp[V] << endl;//初始化状态表memset(dp, 0, sizeof dp);//问题二状态表示 dp[i][j]表示挑选前i个物品，背包体积恰好等于j的所有选法中，最大的价值//先初始化第一行为-1，表示不存在的情况for (int j = 1; j <= V; j++){dp[j] = -1;}//填表for (int i = 1; i <= n; i++){for (int j = v[i]; j <= V; j++){if (dp[j - v[i]] != -1){dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}}//输出结果cout << (dp[V] == -1 ? 0 : dp[V]) << endl;return 0;
}

2.例题

1.零钱兑换1

题目：

算法原理：

根据题意可以看出本道题就是典型的完全背包问题，对应模板题中的问题二，使其背包中恰好装满。

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

状态转移方程：根据当前硬币coins[i-1]（下标映射要减一）选0个，1个，2个等等分为多种情况，因为要找最少硬币个数，所以是所有情况取最小值，这里的推导过程和模板题一样，这里直接写结论：dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i-1]+1])前提条件：j>=coins[i-1]，（注意因为状态值表示的硬币个数，因此当前位置的硬币选多少个，后面要加上对应的个数，这就是为什么后面要+1）。

初始化：dp[0][0]表示从前0个硬币中挑选，总和恰好等于0，最少的硬币个数就是0；除第一行第一个外，其余全部初始化为INF(因为状态转移方程中要取最小值，所以用0x3f3f3f3f，最大值的一半），表示不存在的情况。

填表顺序：从第一行到最后一行，其中每一行从左往右。

返回值：dp[n][amount] >= INF ? -1 : dp[n][amount]，需要先判断一下是否等于INF，如果等于说明从前n个数中挑选，使其总和恰好等于amount不存在，因此返回-1，如果不等于就是存在，返回最小硬币个数。

代码实现：

const int INF = 0x3f3f3f3f;
int coinChange(vector<int>& coins, int amount){int n = coins.size();//状态表示 dp[i][j]表示从前i个硬币中挑选，总和恰好等于j，所有的选法中最少的硬币个数vector<vector<int>> dp(n + 1, vector<int>(amount + 1));//初始化第一行为INF，表示不存在的情况for (int j = 1; j <= amount; j++){dp[0][j] = INF;}//填表for (int i = 1; i <= n; i++){for (int j = 0; j <= amount; j++){dp[i][j] = dp[i - 1][j];if (j >= coins[i-1]){dp[i][j] = min(dp[i][j - coins[i-1]] + 1, dp[i][j]);}}}//返回值return dp[n][amount] >= INF ? -1 : dp[n][amount];
}

空间优化：

int coinChange(vector<int>& coins, int amount){int n = coins.size();//状态表示vector<int> dp(amount + 1);//初始化for (int j = 1; j <= amount; j++){dp[j] = INF;}//填表for (int i = 1; i <= n; i++){for (int j = coins[i - 1]; j <= amount; j++){dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);}}//返回值return dp[amount] == INF ? -1 : dp[amount];
}

2.零钱兑换2

题目：

算法原理：

本道题是上面一道题的变形，挑选硬币使其等于目标值，统计所有的选法。

状态表示：dp[i][j]表示挑选前i个硬币，总和恰好为j的选法总数。

状态转移方程：根据当前硬币coins[i-1]（下标映射要减一）选0个，1个，2个等等分为多种情况，因为要统计所有的选法个数，所以这里是所有情况相加。这里的推导过程以及优化和模板题一样，这里直接写结论：dp[i][j]=dp[i-1][j] + dp[i][j-coins[i-1]（前提条件：j>=coins[i-1]）。

初始化：dp[0][0]表示挑选前0个硬币，总和恰好为0的选法总数，就是1；第一行除dp[0][0]外其余全为0，因为不存在满足条件的选法。

填表顺序：从第一行到最后一行，其中每一行从左往右。

返回值：dp[n][amount]，挑选前n个硬币，总和恰好为amount的选法总数。

代码实现：

int change(int amount, vector<int>& coins){int n = coins.size();//状态表示 dp[i][j]表示挑选前i个硬币，总和恰好为j的选法总数vector<vector<unsigned long long>> dp(n + 1, vector<unsigned long long>(amount + 1));//初始化dp[0][0] = 1;//填表for (int i = 1; i <= n; i++){for (int j = 0; j <= amount; j++){dp[i][j] = dp[i - 1][j];if (j >= coins[i - 1]){dp[i][j] += dp[i][j - coins[i - 1]];}}}//返回值return dp[n][amount];
}

空间优化：

int change(int amount, vector<int>& coins){int n = coins.size();//状态表示vector<unsigned long long> dp(amount + 1);//初始化dp[0] = 1;//填表for (int i = 1; i <= n; i++){for (int j = coins[i-1]; j <= amount; j++){dp[j] = dp[j] + dp[j - coins[i - 1]];}}//返回值return dp[amount];
}

3.完全平方数

题目：

算法原理：

根据题意挑选完全平方数使其等于目标和n，返回使用完全平方数最少的数量。属于完全背包问题中的问题二，并且和零钱兑换1那道题相似，也是找最少数量。

状态表示 ：dp[i][j]表示从前i个数中挑选，平方总和恰好等于j的所有选法中，使用数字最小的个数。

状态转移方程：根据当前完全平方数i*i选0个，1个，2个等等分为多种情况，因为要找最少数量，所以是所有情况取最小值，这里的推导过程和模板题一样，这里直接写结论：dp[i][j]=min(dp[i-1][j],dp[i][j-i*i]+1)前提条件：j>=i*i，（注意因为状态值表示的是个数，因此当前位置的完全平方数选多少个，后面要加上对应的个数，这就是为什么后面要+1）。

初始化：dp[0][0]表示从前0个完全平方数中挑选，总和恰好等于0，最少的个数就是0；除第一行第一个外，其余全部初始化为INF(因为状态转移方程中要取最小值，所以用0x3f3f3f3f，最大值的一半），表示不存在的情况。

填表顺序：从第一行到最后一行，其中每一行从左往右。

返回值：dp[m][n] >= INF ? -1 : dp[m][n]，需要先判断一下是否等于INF，如果等于说明从前m个数中挑选，使其总和恰好等于n不存在，因此返回-1，如果不等于就是存在，返回最少个数。

代码实现：

int numSquares(int n){//m表示可以取得完全平方数范围int m = sqrt(n);//状态表示 dp[i][j]表示从前i个数中挑选，平方总和恰好等于j的所有选法中，使用数字最小的个数vector<vector<int>> dp(m + 1, vector<int>(n + 1));//初始化for (int j = 1; j <= n; j++){dp[0][j] = INF;}//填表for (int i = 1; i <= m; i++){for (int j = 0; j <= n; j++){dp[i][j] = dp[i - 1][j];if(j>=i*i){dp[i][j] = min(dp[i][j - i * i] + 1, dp[i][j]);}}}//返回值return dp[m][n] == INF ? 0 : dp[m][n];
}

空间优化：

int numSquares(int n){int m = sqrt(n);//状态表示vector<int> dp(n + 1);//初始化for (int j = 1; j <= n; j++){dp[j] = INF;}//填表for (int i = 1; i <= m; i++){for (int j = i * i; j <= n; j++){dp[j] = min(dp[j], dp[j - i * i] + 1);}}//返回值return dp[n] == INF ? 0 : dp[n];
}

三.二维费用背包问题

例题

1.一和零

题目：

算法原理：

根据题意要求，从二进制字符串数组中挑选字符串，每个字符串中包含0和1，挑选最多的字符串，使其0的个数不超过m，1的个数不超过n，和01背包问题相比，其实就是多了一个限制条件，因此属于二维费用的01背包问题。

状态表示： dp[i][j][k]表示从前i个字符串中挑选，数字0不超过m个，数字1不超过n个的所有选法中，最长子集的长度。

状态转移方程：根据当前字符串strs[i-1]，选还是不选分情况讨论，如果不选：找到挑选前i-1个字符串，数字0不超过j个，数字1不超过k个的所有选法中，最长的子集长度（用状态表示就是dp[i-1][j][k]）；如果选：假设当前字符串中的0有a个，1有b个，挑选前i-1个字符串时，数字0不超过j-a（其中j>=a），数字1不超过k-b（其中k>=b），（用状态表示就是dp[i-1][j-a][k-b]），因为要找的是最长长度，所以两种情况要取最大值。

初始化：当i=0时，无论怎么选，最长的长度一定为0，所以初始值全部设置为0即可。

返回值：dp[x][m][n]，x表示的是一共有多少个字符串，从前x个字符串中挑选，数字0不超过m个，数字1不超过n个的所有选法中，最长子集的长度。

代码实现：

int findMaxForm(vector<string>& strs, int m, int n){int x = strs.size();//状态表示 dp[i][j][k]表示从前i个字符串中挑选，数字0不超过m个，数字1不超过n个的所有选法中，最长子集的长度vector<vector<vector<int>>> dp(x + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));//初始化 初始值设置为0即可//填表for (int i = 1; i <= x; i++){//统计当前字符串中0和1的个数string cur = strs[i - 1];int a = 0, b = 0;for(auto ch : cur){if (ch == '0'){a++;}else{b++;}}for (int j = 0; j <= m; j++){for (int k = 0; k <= n; k++){//状态转移方程 根据当前字符串选还是不选分情况讨论 两种情况取最大值dp[i][j][k] = dp[i - 1][j][k];if (j >= a && k >= b){dp[i][j][k] = max(dp[i - 1][j - a][k - b] + 1, dp[i][j][k]);}}}}//返回值return dp[x][m][n];
}

空间优化：

int findMaxForm(vector<string>& strs, int m, int n){int x = strs.size();//状态表示vector<vector<int>> dp(m + 1, vector<int>(n + 1));//初始化 初始值全部设置为0//填表for (int i = 1; i <= x; i++){//统计当前字符串中的数字0和1个数string cur = strs[i - 1];int a = 0, b = 0;for(auto ch : cur){if (ch == '0'){a++;}else{b++;}}for (int j = m; j >= a; j--){for (int k = n; k >= b; k--){//状态转移方程dp[j][k] = max(dp[j - a][k - b] + 1, dp[j][k]);}}}//返回值return dp[m][n];
}

2.盈利计划

题目：

算法原理：

根据题意要求，假设数组的长度为x，从前x个工作中挑选，使其需要的员工个数不超过n个，盈利不低于m(minProfit)，当前工作i对应的所选要的员工是group[i-1]，盈利为profit[i-1]（下标从0开始），统计一共有多少种选法。还是属于两个限制条件的01背包问题。

状态表示：dp[i][j][k]表示从前i个计划中挑选，员工个数不超过j，盈利不低于k，一共有多少种选法。

状态转移方程：根据当前的工作i选还是不选分两种情况讨论，如果不选：就是从前i-1个工作中挑选，使其员工个数不超过j，盈利不低于k，用状态表示就是dp[i-1][j][k]；如果选：就是从前i-1个工作中挑选，使其员工个数不超过j-group[i-1]，（前提条件，j>=group[i-1]），盈利不低于k-profit[i-1]（注意，因为这里的盈利是不低于，所以即使k<profit[i-1]，也依然是可以的，但是因为不存在负数的情况，所以如果当k-profit[i-1]小于0时，取0即可）。因为要统计所有的选法，所以两种情况相加。

初始化：当i=0，k=0时，dp[0][j][0]表示从前0个工作中挑选，员工个数不超过j，盈利不低于0，保证不选即可，因此选法个数就是1。

返回值：dp[x][n][m]，从前x个工作中挑选，使其员工个数不超过n，盈利不低于m，一共有多少种选法。

代码实现：

const int N = 1000000007;
int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit){int x = group.size();//状态表示 dp[i][j][k]表示从前i个计划中挑选，员工个数不超过j，盈利不低于k，总的选法个数vector<vector<vector<int>>> dp(x + 1, vector<vector<int>>(n + 1, vector<int>(m + 1)));//初始化 dp[0][j][0]表示从前0个计划中挑选，员工个数不超过j,盈利不低于0，选法个数为1for (int j = 0; j <= n; j++){dp[0][j][0] = 1;}//填表for (int i = 1; i <= x; i++){for (int j = 0; j <= n; j++){for (int k = 0; k <= m; k++){//状态转移方程 根据当前计划选还是不选分情况讨论//不选dp[i][j][k] = dp[i - 1][j][k];//选 if (j >= group[i - 1]){dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];}dp[i][j][k] %= N;}}}//返回值return dp[x][n][m];
}

空间优化：

int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit){int x = group.size();//状态表示vector<vector<int>> dp(n + 1, vector<int>(m + 1));//初始化for (int j = 0; j <= n; j++){dp[j][0] = 1;}//填表for (int i = 1; i <= x; i++){for (int j = n; j >= group[i - 1]; j--){for (int k = m; k >= 0; k--){dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];dp[j][k] %= N;}}}//返回值return dp[n][m];
}

以上就是关于动态规划中背包问题练习题的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！