Length of longest subset consisting of A 0s and B 1s from an array of strings

#include <bits/stdc++.h>

using namespace std;

  

int count0(string s)

{

    

    int count = 0;

  

    

    for (int i = 0; i < s.size(); i++) {

  

        

        if (s[i] == '0') {

            count++;

        }

    }

    return count;

}

int solve(vector<string> vec, int A,

          int B, int idx,

          vector<vector<vector<int> > >& dp)

{

    

    

    if (idx == vec.size() || A + B == 0) {

        return 0;

    }

    

    if (dp[A][B][idx] > 0) {

        return dp[A][B][idx];

    }

  

    

    int zero = count0(vec[idx]);

  

    

    int one = vec[idx].size() - zero;

  

    

    

    int inc = 0;

  

    

    

    if (zero <= A && one <= B) {

        inc = 1

              + solve(vec, A - zero,

                      B - one, idx + 1, dp);

    }

  

    

    

    int exc = solve(vec, A, B, idx + 1, dp);

  

    

    dp[A][B][idx] = max(inc, exc);

  

    

    return dp[A][B][idx];

}

  

int MaxSubsetlength(vector<string> arr,

                    int A, int B)

{

    

    vector<vector<vector<int> > > dp(

        A + 1,

        vector<vector<int> >(B + 1,

                             vector<int>(arr.size() + 1,

                                         0)));

    

    return solve(arr, A, B, 0, dp);

}

  

int main()

{

    vector<string> arr = { "1", "0", "10" };

    int A = 1, B = 1;

  

    cout << MaxSubsetlength(arr, A, B);

    return 0;

}

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets