Ones and Zeroes หาสตริงไบนารีสูงสุดภายใต้ข้อจำกัด 0 และ 1 ใน C++

มี m ตัว 0 และ n ตัว 1 ให้อาร์เรย์สตริงไบนารี หาจำนวนสตริงสูงสุดที่สร้างได้ (แต่ละ 0 และ 1 ใช้ได้สูงสุด 1 ครั้ง)

ตัวอย่าง: ["10","0001","111001","1","0"], m=5, n=3 → 4 สตริง ("10","0001","1","0")

วิธีแก้ปัญหา (0/1 Knapsack 2D DP)

1. DP table dp[m+1][n+1] = จำนวนสตริงสูงสุด
2. วนทุกสตริง str:
   • นับ one, zero ใน str
   • วน j = m ถึง zero, k = n ถึง one (ย้อนกลับเพื่อ 0/1 knapsack):
     • dp[j][k] = max(dp[j][k], 1 + dp[j-zero][k-one])
     • อัปเดต ret = max(ret, dp[j][k])
3. คืนค่า ret

ตัวอย่างโค้ด C++

#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, zero = 0;
            for (char c : strs[i]) {
                one += (c == '1');
                zero += (c == '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;
    }
};

int main() {
    vector<string> v = {"10","0001","111001","1","0"};
    Solution ob;
    cout << ob.findMaxForm(v, 5, 3);
    return 0;
}

Input

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

Output

4