algo-aha

最多能选几个01串

• https://leetcode.com/problems/ones-and-zeroes/

int findMaxForm(vector<string>& strs, int m, int n) {
    // 选子集，01背包问题，两维代价m和n
    // 设dp[k][i][j]表示前k个串、剩余i个0和j个1时可得的最大个数
    // dp[k][i][j] = max{ dp[k-1][i][j], 1 + dp[k-1][i-(0s)_k][j-(1s)_k] /*选不选第k个串*/ }
    // 递推式在k这维上只依赖k-1项，可省掉k这维，k仍从左往右遍历
    // dp[i][j] = max{ dp[i][j], 1 + dp[i-(0s)_k][j-(1s)_k] }
    // dp[i-(0s)_k][j-(1s)_k]要表示旧状态，i、j从右往左遍历
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (const auto &str: strs) {
        int zeros = 0, ones = 0;
        for (char c : str) {
            if (c == '0') zeros++;
            else ones++;
        }
        // 01背包，逆序遍历容量
        for (int i = m; i >= zeros; i--) {
            for (int j = n; j >= ones; j--) {
                dp[i][j] = max( dp[i][j], 1 + dp[i - zeros][j - ones] );
            }
        }
    }
    return dp[m][n];
}

有利可图的方案数

• https://leetcode.com/problems/profitable-schemes/

int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
    // 设dp[i][g][p]表示前i个案件、g人至少p利润时的方案数
    // dp[i][g][p] = dp[i-1][g][p] + dp[i-1][g-group[i]][max(0, p-profit[i])] )
    // 当p-profit[i]为负时要求“至少负利润”，这是都能达到的，等价于“至少0利润”，所以用max(0, p-profit[i])
    // 初始dp[0][0][0] = 1
    // 省掉i这维，i仍从左往右遍历。01背包问题，两维代价，逆序遍历
    const int MOD = 1e9 + 7;
    const int N = group.size();
    vector<vector<int>> dp(G + 1, vector<int>(P + 1, 0));
    dp[0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int g = G; g >= group[i]; g--) {
            for (int p = P; p >= 0; p--) {
                dp[g][p] = (dp[g][p] + dp[g - group[i]][max(0, p - profit[i])]) % MOD;
            }
        }
    }
    
    int ans = 0;
    for (int g = 0; g <= G; g++) {
        ans = (ans + dp[g][P]) % MOD;
    }
    return ans;
}