JavaScriptで0と1を使って形成できる文字列の数を動的計画法で求める方法

問題概要

「0」と「1」のみで構成された文字列の配列 arr を第1引数として受け取るJavaScript関数を作成します。

第2引数と第3引数には、それぞれ2つの整数 m と n が渡されます。この関数の役割は、配列 arr の中から、最大 m 個の「0」と最大 n 個の「1」を使用して形成できる文字列がいくつあるかを求めることです。

入力例

const arr = ["10", "0001", "111001", "1", "0"];
const m = 5, n = 3;

出力例

const output = 4;

出力の説明

5個の「0」と3個の「1」を使って形成できる文字列は、以下の4つです。

"10", "0001", "1", "0"

なお「111001」には1が4つ含まれているため、利用できる「1」の上限（3個）を超えてしまい、選択することはできません。

解法のポイント：動的計画法（DP）

この問題は、いわゆる「0/1ナップサック問題」の応用として捉えることができます。各文字列を1つのアイテムとみなし、「0の使用可能数」と「1の使用可能数」という2つの制約を持つナップサックに、最大でいくつのアイテムを詰め込めるかを求めるイメージです。

具体的な手順は以下の通りです。

• まず、各文字列に含まれる「0」と「1」の個数をカウントします。
• 次に、(m+1) × (n+1) のサイズを持つ二次元DPテーブルを用意します。dp[j][k] は「0を最大 j 個、1を最大 k 個使って形成できる文字列の最大数」を表します。
• 各文字列について、テーブルを大きいインデックス側から順に更新していきます。これにより、同一の文字列が重複してカウントされるのを防ぐことができます。

状態遷移は次の式で表されます。

dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1);

実装コード

const arr = ["10", "0001", "111001", "1", "0"];
const m = 5, n = 3;
const findAllStrings = (arr = [], m = 1, n = 1) => {
    const getCount = str => str.split('').reduce((acc, cur) => {
        cur === '0' ? acc.zeros++ : acc.ones++;
        return acc;
    }, {zeros:0, ones:0});
    const dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
    for(let i = 0; i < arr.length; i++) {
        const {zeros, ones} = getCount(arr[i]);
        for(let j = m; j >= zeros; j--) {
            for(let k = n; k >= ones; k--) {
                dp[j][k] = Math.max(dp[j-zeros][k-ones]+1, dp[j][k]);
            }
        }
    }
    return dp[m][n]
};
console.log(findAllStrings(arr, m, n));

出力結果

コンソールには以下の値が出力されます。

4