C++-এ ১ এবং ০

ধরুন আমাদের m টি 0 এবং n টি 1-এর একটি ডোমিনেটর আছে। অন্যদিকে, বাইনারি স্ট্রিংয়ের একটি অ্যারে আছে। এখন আমাদের কাজ হল দেওয়া m 0 এবং n 1 দিয়ে আমরা সর্বোচ্চ কতগুলো স্ট্রিং জেনারেট করতে পারি তা বের করা। প্রতিটি 0 এবং 1 সর্বোচ্চ একবার ব্যবহার করা যাবে। তাই যদি ইনপুট হয় Array = [“10”, “0001”, “111001”, “1”, “0”,] এবং m = 5 এবং n = 3, তবে আউটপুট হবে 4। কারণ 5 টি 0 এবং 3 টি 1 ব্যবহার করে মোট 4টি স্ট্রিং তৈরি করা যায়, যেগুলি হল “10,”0001”,”1”,”0”।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −

(m + 1) x (n + 1) আকারের একটি ম্যাট্রিক্স তৈরি করুন
ret := ০
i = 0 থেকে strs অ্যারেতে আকার পর্যন্ত
- one := 0, zero := 0
- j = 0 থেকে strs[i]-এর আকার পর্যন্ত
  - যদি star[i, j] 1 হয় তবে one বৃদ্ধি করুন, অথবা 0 হলে zero বৃদ্ধি করুন
- j = m থেকে ০ পর্যন্ত নিচের দিকে
  - k = n থেকে one পর্যন্ত নিচের দিকে
    - dp[j,k] := dp[j,k] এবং 1 + dp[j – zero, k - one]-এর max
    - ret := ret এবং dp[j,k]-এর max
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;    } }; main(){    vector<string> v = {"10","0001","111001","1","0"};    Solution ob;    cout << (ob.findMaxForm(v, 5, 3)); }

ইনপুট

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