給你一個二進(jìn)制字符串?dāng)?shù)組 strs 和兩個整數(shù) m 和 n 。
請你找出并返回 strs 的最大子集的大小，該子集中 最多 有 m 個 0 和 n 個 1 。
如果 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 。

提示：
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 僅由 ‘0’ 和 ‘1’ 組成
1 <= m, n <= 100

這道題同樣是01背包的問題，但是不好看出來，我們來分析一下：
每個字符串?dāng)?shù)組中的字符串都只會使用一次，所以符合01背包特點；
m 和 n 就類似于背包容量，但是這里卻是二維的；
strs就相當(dāng)于物品
相對應(yīng)的我們可以將每個字符串1和0的個數(shù)求出來，就相當(dāng)于物品的重量
字符串的個數(shù)就相當(dāng)于物品價值

接下來就可以分析解題步驟了
1，dp[i][j]是 i 個0和 j 個1的strs的最大子集大小
2，dp[i][j] 可以由前一個strs里的字符串推導(dǎo)出來，strs里的字符串有zeronums個0，onenums個1。
dp[i][j] 就可以是 dp[i - zeronums][j - onenums] + 1，取最大值后即
dp[i][j] = max(dp[i][j], dp[i - zeronums][j - onenums] + 1);
3，物品價值不會為負(fù)，所以初始化都為0即可
4，遍歷順序依舊是外面是物品正序遍歷，里面是背包大小逆序遍歷；

代碼如下：

class Solution { public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (auto str : strs) {int zeronums = 0, onenums = 0;for (auto ch : str) {if (ch == '0') zeronums++;else onenums++;}for (int i = m; i >=zeronums; --i) {for(int j = n; j >= onenums; --j) {dp[i][j] = max(dp[i][j], dp[i - zeronums][j - onenums] + 1);}}}return dp[m][n];} };

總結(jié)

這道題關(guān)鍵是對二維背包的理解，了解01背包有這種形式。

總結(jié)

以上是生活随笔為你收集整理的一和零(二维01背包)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。