474. 一和零-Toy模板网

这篇具有很好参考价值的文章主要介绍了474. 一和零。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、题目描述

2、思路：动态规划01背包

2.1、确定dp数组及下标含义

2.2、确定递归数组

2.3、初始化

2.4、确定遍历顺序

1、题目描述

给你一个二进制字符串数组 strs 和两个整数 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ones-and-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、思路：动态规划01背包

根据题目描述可以知道，返回最大子集长度，子集中最多有m个0和n个1 。

其实可以理解为，每一个01字符串都代表了一个权重为j个0，k个1 的物体，而我们的背包大小也有两个权重，一个是m一个是n。那么问题就可以翻译为，一个权重为m|n的背包最多可以放几个物体，而且每个物体不可以重复拿取，这样问题便成为了01背包问题。

2.1、确定dp数组及下标含义

dp[j][k]表示了背包大小为i j时能容纳的最大子集长度。

2.2、确定递归数组

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

2.3、初始化

背包大小为0|0时，因为字符串最小长度为1，能放的字符串为0，故初始化为0，其余的dp数组根据其他的数组得来，初始化为最小非负数0 。

2.4、确定遍历顺序

最外层单层for循环从前往后遍历所有的物品（字符串），内层两个for循环从小到大遍历背包。

、文章来源地址https://www.toymoban.com/news/detail-436119.html

C++实现如下：

#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];
    }
};

到了这里，关于474. 一和零的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！