目錄

1、題目描述

2、思路：動(dòng)態(tài)規(guī)劃01背包

2.1、確定dp數(shù)組及下標(biāo)含義

2.2、確定遞歸數(shù)組

2.3、初始化

2.4、確定遍歷順序

1、題目描述

給你一個(gè)二進(jìn)制字符串?dāng)?shù)組 strs 和兩個(gè)整數(shù) m 和 n 。

請(qǐng)你找出并返回 strs 的最大子集的長度，該子集中 最多 有 m 個(gè) 0 和 n 個(gè) 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

輸入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
輸出：4
解釋：最多有 5 個(gè) 0 和 3 個(gè) 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他滿足題意但較小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不滿足題意，因?yàn)樗?4 個(gè) 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

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/ones-and-zeroes
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2、思路：動(dòng)態(tài)規(guī)劃01背包

根據(jù)題目描述可以知道，返回最大子集長度，子集中最多有m個(gè)0和n個(gè)1 。

其實(shí)可以理解為，每一個(gè)01字符串都代表了一個(gè)權(quán)重為j個(gè)0，k個(gè)1 的物體，而我們的背包大小也有兩個(gè)權(quán)重，一個(gè)是m一個(gè)是n。那么問題就可以翻譯為，一個(gè)權(quán)重為m|n的背包最多可以放幾個(gè)物體，而且每個(gè)物體不可以重復(fù)拿取，這樣問題便成為了01背包問題。

2.1、確定dp數(shù)組及下標(biāo)含義

dp[j][k]表示了背包大小為i j時(shí)能容納的最大子集長度。

2.2、確定遞歸數(shù)組

dp[j][k]?=?max(dp[j][k],dp[j-str[i][0]][k-str[i][1]]+1);

2.3、初始化

背包大小為0|0時(shí)，因?yàn)樽址钚￠L度為1，能放的字符串為0，故初始化為0，其余的dp數(shù)組根據(jù)其他的數(shù)組得來，初始化為最小非負(fù)數(shù)0 。

2.4、確定遍歷順序

最外層單層for循環(huán)從前往后遍歷所有的物品（字符串），內(nèi)層兩個(gè)for循環(huán)從小到大遍歷背包。

、文章來源地址http://www.zghlxwxcb.cn/news/detail-436119.html

C++實(shí)現(xiàn)如下：

#include<iostream>
#include<vector>
using namespace std; 
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int length = strs.size();
//        int str[length][2];
        vector<vector<int> > str(length,vector<int>(2,0));
        
        for(int i = 0;i<length;++i){
            for(int j = 0;j<strs[i].size();++j){
                if(strs[i][j]=='0'){
                    str[i][0]+=1;
                }
            }
            str[i][1] = strs[i].size() - str[i][0];
        }
        vector<vector<int> > dp(m+1,vector<int>(n+1,0));
		
        for(int i = 0;i<length;++i){
            for(int j = m;j>=str[i][0];--j){
                for(int k = n;k>=str[i][1];--k){
                    dp[j][k] = max(dp[j][k],dp[j-str[i][0]][k-str[i][1]]+1);
                }
            }
        }

        return dp[m][n];
    }
};

到了這里，關(guān)于474. 一和零的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！