✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：动态规划篇–CSDN博客
文章目录
- 一.01背包问题
- 1.模板题
- 2.例题
- 1.分割等和子集
- 2.目标和
- 3.最后一块石头的重量
- 二.完全背包问题
- 1.模板题
- 2.例题
- 1.零钱兑换1
- 2.零钱兑换2
- 3.完全平方数
- 三.二维费用背包问题
- 例题
- 1.一和零
- 2.盈利计划
一.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的最大价值
//初始值全部设置为0
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][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的最大价值
//第一行除第一个外，其他全初始值设置为-1
for (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个数，所有的选法中，能否恰好等于j
vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1,true));
//初始化 添加第0行和第0列,除第一行外其余全部为true
for (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，选法个数为1
for (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];
}
以上就是关于动态规划中背包问题练习题的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
