leetcode 474 Ones and Zeroes 双维度01背包问题

题目

https://leetcode.com/problems/ones-and-zeroes/submissions/

思路

双维度 01 背包问题,m,n是容量,value 都是1,遍历个数,遍历容量,对容量进行状态压缩

源码

class Solution {
public:
    vector<int> ones;
    vector<int> zeros;
    vector<vector<int>> mn;
    int findMaxForm(vector<string>& strs, int m, int n) {
        if(strs.size()==0)return 0;
        if(m==0&&n==0)return 0;
        ones.resize(strs.size());
        zeros.resize(strs.size());
        mn.resize(m+1,vector<int>(n+1,0));
        for(int i = 0;i < strs.size();++i){
            int o = 0;
            for(int k = 0;k < strs[i].size();++k){
                if(strs[i][k]=='1')o++;
            }
            ones[i]=o;
            zeros[i]=strs[i].length()-o;
        }
        //bag
        for(int i = 0;i < strs.size();++i){
            //cout<<endl <<i<<endl;
            for(int m1 = m;m1>=zeros[i];--m1){
                for(int n1 = n;n1>=ones[i];--n1){
                    mn[m1][n1]=max(mn[m1][n1],mn[m1-zeros[i]][n1-ones[i]]+1);
                    //cout <<m1<<","<<n1<<" = "<<mn[m1][n1]<<endl;
                }
            }
        }
        return mn[m][n];
    }
};

发表评论

邮箱地址不会被公开。 必填项已用*标注