C++ এ এক এবং শূন্য

ধরুন আমাদের যথাক্রমে m 0s এবং n 1s এর একটি ডমিনেটর আছে। অন্যদিকে, বাইনারি স্ট্রিং সহ একটি অ্যারে রয়েছে। এখন আমাদের কাজ হল প্রদত্ত m 0s এবং n 1s দিয়ে সর্বাধিক সংখ্যক স্ট্রিং তৈরি করা। প্রতিটি 0 এবং 1 সর্বাধিক একবার ব্যবহার করা যেতে পারে। সুতরাং ইনপুট যদি হয় Array =[“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
আমি ০ থেকে স্ট্রস অ্যারের আকারের মধ্যে
- এক :=0, শূন্য :=0
- j-এর জন্য রেঞ্জ 0 থেকে strs এর আকার [i]
  - স্টার[i, j] 1 হলে একটি বাড়ান, অথবা 0 হলে শূন্য বাড়ান
- m রেঞ্জে j-এর জন্য 0
  - j এর জন্য রেঞ্জ n থেকে নিচের দিকে
    - dp[j,k] :=dp[j,k] এর সর্বোচ্চ এবং 1 + dp[j – শূন্য, k - one]
    - ret :=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