二维背包问题（C++）
文章目录
- 前言
- 474. 一和零
- 1.状态表示
- 2.状态转移方程
- 3.初始化
- 4.填表顺序
- 5.返回值是什么
- 6.代码编写
- 7.代码优化
- 总结
前言
二维背包问题和基础背包问题的解题思路是一样的，唯一不同的就是二维背包是有两个限制条件，而一维背包只有一个限制条件。
474. 一和零
474. 一和零
1.状态表示
我们根据经验+题目要求，确定出状态标示：
dp[i][j][k]:从前i个字符串中挑选，字符0的个数恰好为j，字符1的个数恰好为k，此时的最多字符串个数。
2.状态转移方程
根据最后一个位置的情况划分问题
🌟如果i位置没有选，此时dp[i][j][k]=dp[i-1][j][k];
🌟如果i位置选择了，我们要保证字符0和1出现的次数必须等于j和k。
假设i位置字符串中字符0的个数为a,字符1的个数为b,我们必须满足
j-a>=0&&k-b>=0;
此时dp[i][j][k]=dp[i-1][j-a][k-b]+1;
🌟我们最终的dp[i][j][k]就是上面两种的最大值。
3.初始化
我们要多开一行，一列以及一高。
🌟全部初始化为0
🌟注意下标的映射
4.填表顺序
我们只需要保证i从小值填到大只就可以
5.返回值是什么
返回dp[len][m][n]的值即可
6.代码编写
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int len=strs.size();//建表+初始化vector<vector<vector<int>>>dp(len+1,vector<vector<int>>(m+1,vector<int>(n+1,0)));//填表+下标映射for(int i=1;i<=len;i++){//统计个数int a=0;int b=0;for(auto&e:strs[i-1]){if(e=='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][j][k],dp[i-1][j-a][k-b]+1);}}}//返回值return dp[len][m][n];}
};
7.代码优化
代码优化与一维01背包是相同的，利用滚动数组
填表顺序要保证从右往左
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int len=strs.size();//建表+初始化vector<vector<int>>dp(m+1,vector<int>(n+1,0));//填表+下标映射for(int i=1;i<=len;i++){//统计个数int a=0;int b=0;for(auto&e:strs[i-1]){if(e=='0') a++;else b++;}//01背包，注意填表顺序从右往左for(int j=m;j>=a;j--){for(int k=n;k>=b;k--){dp[j][k]=max(dp[j][k],dp[j-a][k-b]+1);}}}//返回值return dp[m][n];}
};
总结
以上就是今天要讲的内容，本文仅仅详细介绍了 。希望对大家的学习有所帮助，仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘