หนึ่งและศูนย์ใน C++

สมมติว่าเรามีผู้ปกครองของ m 0s และ n 1s ตามลำดับ ในทางกลับกัน มีอาร์เรย์ที่มีสตริงไบนารี ตอนนี้งานของเราคือค้นหาจำนวนสตริงสูงสุดที่เราสามารถสร้างได้ด้วย m 0s และ n 1s ที่กำหนด แต่ละ 0 และ 1 สามารถใช้ได้สูงสุดครั้งเดียว ดังนั้นหากอินพุตเป็นเหมือน Array =[“10”, “0001”, “111001”, “1”, “0”,] และ m =5 และ n =3 ผลลัพธ์จะเป็น 4 นั่นเป็นเพราะมี ทั้งหมด 4 สตริงสามารถสร้างโดยใช้ 5 0s และ 3 1s ซึ่งก็คือ “10,0001”,”1”,”0”.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างเมทริกซ์ขนาด (m + 1) x (n + 1)
• ret :=0
• สำหรับฉันในช่วง 0 ถึงขนาดของอาร์เรย์ strs
  • หนึ่ง :=0, ศูนย์ :=0
  • สำหรับ j ในช่วง 0 ถึงขนาดของ strs[i]
    • เพิ่ม 1 เมื่อ star[i, j] เป็น 1 หรือเพิ่มศูนย์เมื่อเป็น 0
  • สำหรับ j ในช่วง m ลงไปที่ 0
    • สำหรับ j ในช่วง n ลงไปที่หนึ่ง
      • dp[j,k] :=สูงสุดของ dp[j,k] และ 1 + dp[j – ศูนย์, k - หนึ่ง]
      • 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

ผลลัพธ์

4