Ones và Zeroes trong C ++

Giả sử chúng ta có một thống trị tương ứng là m 0s và n 1s. Mặt khác, có một mảng với các chuỗi nhị phân. Bây giờ nhiệm vụ của chúng ta là tìm số chuỗi tối đa mà chúng ta có thể tạo ra với m 0 và n 1 cho trước. Mỗi 0 và 1 có thể được sử dụng nhiều nhất một lần. Vì vậy, nếu đầu vào giống như Array =[“10”, “0001”, “111001”, “1”, “0”,] và m =5 và n =3, thì đầu ra sẽ là 4. Điều này là do có hoàn toàn có thể tạo ra 4 chuỗi bằng cách sử dụng 5 số 0 và 3 số 1, là “10,” 0001 ”,“ 1 ”,” 0 ”.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo ma trận có kích thước (m + 1) x (n + 1)
• ret:=0
• cho tôi trong phạm vi từ 0 đến kích thước của mảng strs
  • một:=0, không:=0
  • cho j trong phạm vi 0 đến kích thước của strs [i]
    • tăng một khi dấu sao [i, j] là 1 hoặc tăng 0 khi dấu sao là 0
  • cho j trong phạm vi m xuống 0
    • cho j trong phạm vi n xuống một
      • dp [j, k]:=max của dp [j, k] và 1 + dp [j - zero, k - one]
      • ret:=max của ret và dp [j, k]
• trả lời lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

4