सी++ में ओन्स और जीरो

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

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

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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