01背包
把字符串看成物品,每个重量为1,
对于每个物品选与不选两种
只能选一次。选的时候方案体积+1.
int findMaxForm(vector<string>& strs, int m, int n) {
// 01背包,选和不选
vector<vector<int>> f(m + 1, vector<int>(n+1, 0)); //二维。
// 每个字符串看成一个物品;
// 一位体积: 0重量,1体积 价值1
//
for (string &str : strs) //从前往后枚举每一个物品
{
int cnt_m = 0, cnt_n = 0;
for (char &c : str)
{
if (c == '0') cnt_m++; //0的个数,计入m里
else cnt_n ++; //1的个数,计入n里
}
//由于每个物品只能选一次,从大到小枚举。
for (int i = m; i >= cnt_m; i--)
for (int j = n; j >= cnt_n; j--)
f[i][j] = max(f[i][j], f[i - cnt_m][j - cnt_n] + 1); //选了就体积+1,要尽量选体积大的方案MAX
}
return f[m][n];
}