C++ में एक और शून्य

मान लीजिए हमारे पास m 0s और n 1s का एक प्रभुत्व है। दूसरी ओर, बाइनरी स्ट्रिंग्स के साथ एक सरणी है। अब हमारा कार्य दिए गए m 0s और n 1s के साथ उत्पन्न होने वाली स्ट्रिंग्स की अधिकतम संख्या ढूंढना है। प्रत्येक 0 और 1 का उपयोग अधिकतम एक बार किया जा सकता है। इसलिए यदि इनपुट सरणी = ["10", "0001", "111001", "1", "0",] और m = 5 और n = 3 है, तो आउटपुट 4 होगा। ऐसा इसलिए है क्योंकि 5 0s और 3 1s के उपयोग से कुल 4 स्ट्रिंग्स बनाई जा सकती हैं, जो हैं "10", "0001", "1", "0"।

हल का दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• आकार (m+1) x (n+1) की एक मैट्रिक्स बनाएं
• ret := 0
• i = 0 से strs सरणी का आकार तक:
  • one := 0, zero := 0
  • j = 0 से strs[i] का आकार तक:
    • जब strs[i][j] 1 हो तो one बढ़ाएं, या जब 0 हो तो zero बढ़ाएं
  • j = m से 0 तक नीचे:
    • k = n से one तक नीचे:
      • dp[j][k] := max(dp[j][k], 1 + dp[j-zero][k-one])
      • ret := max(ret, dp[j][k])
• ret लौटाएं

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int findMaxForm(vector<string>& strs, int m, int n) { 
        vector<vector<int>> dp(m + 1, vector<int>(n + 1)); 
        int ret = 0; 
        for(int i = 0; i < strs.size(); i++){ 
            int one = 0; 
            int zero = 0; 
            for(int j = 0; j < strs[i].size(); j++){ 
                one += strs[i][j] == '1'; 
                zero += strs[i][j] == '0'; 
            } 
            for(int j = m; j >= zero; j--){ 
                for(int k = n; k >= one; k--){ 
                    dp[j][k] = max(dp[j][k], 1 + dp[j - zero][k - one]); 
                    ret = max(ret, dp[j][k]); 
                } 
            } 
        } 
        return ret; 
    } 
}; 

int main(){ 
    vector<string> v = {"10","0001","111001","1","0"}; 
    Solution ob; 
    cout << (ob.findMaxForm(v, 5, 3)); 
}

इनपुट

["10","0001","111001","1","0"] 5 3

आउटपुट

4