C++でm個の0とn個の1から作成できる最大の文字列数を求める動的計画法の解法

問題概要

m個の0とn個の1が与えられているとします。さらに、バイナリ文字列からなる配列があります。ここでの課題は、与えられたm個の0とn個の1を使用して生成できる文字列の最大数を求めることです。ただし、各0と1はそれぞれ一度しか使用できません。

例えば、配列が ["10", "0001", "111001", "1", "0"]、m = 5、n = 3 の場合、出力は4になります。これは、5つの0と3つの1を使って「10」「0001」「1」「0」の合計4つの文字列を作ることができるためです。

解法のアプローチ

この問題は動的計画法（DP）を用いて効率的に解くことができます。手順は以下の通りです。

• (m + 1) × (n + 1) のサイズを持つ2次元配列 dp を作成する
• 答えを格納する変数 ret を 0 で初期化する
• 配列 strs の各文字列について以下を繰り返す：
  • その文字列に含まれる '1' の個数 one と '0' の個数 zero を数える
  • j を m から zero まで降順に、k を n から one まで降順にループさせる（降順にすることで同じ文字列を二重に使用してしまうことを防げます）
    • dp[j][k] を dp[j][k] と 1 + dp[j - zero][k - one] の大きい方で更新する
    • ret を ret と dp[j][k] の大きい方で更新する
• 最後に 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;
            int zero = 0;
            // 文字列内の0と1の個数をカウント
            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

まとめ

このアルゴリズムは、0-1ナップサック問題の応用と考えることができます。各文字列を「アイテム」とみなし、そのアイテムを選ぶために必要なコストが0の個数と1の個数であると捉えます。時間計算量は O(L × m × n)（Lは文字列の総長）、空間計算量は O(m × n) となり、非常に効率的な解法です。