Số 0 và 1 (Ones and Zeroes) trong C++

Cho m số 0 và n số 1. Mảng chuỗi nhị phân strs. Tìm số chuỗi tối đa có thể tạo được (mỗi 0/1 dùng tối đa 1 lần).

Ví dụ: strs=["10","0001","111001","1","0"], m=5, n=3 → 4 chuỗi ("10","0001","1","0").

Thuật toán (DP 2D - Knapsack 0/1)

1. DP dp[i][j] = số chuỗi max dùng i số 0 và j số 1.
2. Duyệt từng chuỗi, đếm zero, one.
3. Cập nhật DP ngược: for i=m..zero, j=n..one: dp[i][j] = max(dp[i][j], 1+dp[i-zero][j-one]).

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findMaxForm(vector& strs, int m, int n) {
        vector> dp(m+1, vector(n+1,0));
        int ret=0;
        for (string& s : strs) {
            int zero=0, one=0;
            for (char c : s) { if (c=='0') zero++; else one++; }
            for (int i=m; i>=zero; i--)
                for (int j=n; j>=one; j--) {
                    dp[i][j] = max(dp[i][j], 1 + dp[i-zero][j-one]);
                    ret = max(ret, dp[i][j]);
                }
        }
        return ret;
    }
};

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

Đầu vào / Đầu ra

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

Output: 4