指定された条件に従って配列から長さ K のバイナリ文字列を構築します

このチュートリアルでは、長さ K のバイナリ文字列を構築する必要があります。配列要素を使用してサブセットの合計が I に等しい場合、その i 番目のインデックスには次の値が含まれている必要があります。 「1」。問題を解決する 2 つの方法を学びます。最初のアプローチでは、動的プログラミング手法を使用して、サブセットの合計がインデックス "I" に等しい可能性があるかどうかを確認します。 2 番目の方法では、bitset を使用して、配列要素から可能なすべての合計を見つけます。

問題文 - N個の整数を含む配列が与えられています。さらに、バイナリ文字列の長さを表す整数 M が与えられます。次の条件を満たすように、長さ M のバイナリ文字列を作成する必要があります。

• インデックス「I」の文字は、合計がインデックス「I」に等しいサブセットを配列から見つけることができた場合は 1、それ以外の場合は 0 になります。

• 私のインデックスは 1 から始まります。

例例

イラスト

• 合計が 1 に等しいサブセットは {1} です。

• 合計が 2 に等しいサブセットは {2} です。

• 合計が 3 に等しいサブセットは {1, 2} です。

• 合計が 4 になるサブセットが見つからないため、4 番目のインデックスに 0 を置きます。

イラスト

合計が 1 ～ 5 になるように、考えられるすべての組み合わせを作成できます。したがって、最初の 5 文字は 1、最後の 4 文字は 0 になります。

イラスト

配列要素を使用して 1 と 4 に等しい合計を取得することはできないため、最初と 4 番目のインデックス位置に 0 を配置します。

方法1

このメソッドでは、動的プログラミングを使用して、配列要素を使用してインデックス 'I' に等しい合計を構築できるかどうかを確認します。インデックスごとにそれをチェックし、バイナリ文字列に 1 または 0 を追加します。

• ステップ 1

  - サイズ N のベクトルを作成し、整数値で初期化します。また、文字列型の「bin」変数を定義し、空の文字列で初期化します。

• ステップ 2

  - for ループを使用して、反復の合計数を文字列の長さと等しくします。

• ステップ 3

  - for ループで、配列 N とインデックス値をパラメーターとして渡して isSubsetSum() 関数を呼び出します。

• ステップ 4

  - isSubsetSum() 関数が true を返した場合は、「bin」に「1」を追加します。それ以外の場合は、「bin」に「0」を追加します。

• ステップ 5

  - isSubsetSum() 関数を定義して、配列要素を使用して合計を実行できるかどうかを確認します。

• ステップ 5.1

  - dpTable という名前の 2 次元ベクトルを定義します。

• ステップ 5.2

  - 合計がゼロになる可能性があるため、「dpTable[i][0]」を true に初期化します。ここで、「I」はインデックス値です。

• ステップ 5.3

  - 空の配列の合計は不可能であるため、「dpTable[0][j]」を false に初期化します。

• ステップ 5.4

  - 次に、2 つのネストされたループを使用します。最初のループは 1 から N まで反復し、もう 1 つのループは 1 から合計まで反復します。

• ステップ 5.5

  - for ループで、現在の要素の値が合計より大きい場合は、それを無視します。

• ステップ 5.6

  -それ以外の場合、要素を含めるか除外して合計を取得します。

• ステップ5.7

  -結果を含む「dpTable[N][sum]」を返します。

  ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
時間計算量 - O(N^3)。isSubsetSum() の時間計算量は O(N^2) で、ドライバー コード内で N 回呼び出すためです。

isSubsetSum() 関数で 2 次元ベクトルを使用するため、空間複雑度 - O(N^2)。

ビットセットの使用方法

このメソッドでは、ビットセットを使用して、配列のさまざまな要素を組み合わせて、考えられるすべての合計値を見つけます。ここで、bitset はバイナリ文字列を作成することを意味します。結果として得られるビット セットの各ビットは、合計が特定のインデックスに等しいかどうかを表しており、ここでそれを見つける必要があります。

- 配列と M を定義します。さらに、createBinaryString() 関数を定義します。

• ステップ 2

  - 次に、バイナリ文字列を作成する必要な長さのビットのセットを定義します。

• ステップ 3

  - 合計は常に 0 になる可能性があるため、ビット [0] を 1 に初期化します。

• ステップ 4

  - for ループを使用して、配列要素を反復処理します。

• ステップ 5

  - まず、配列要素に対して「ビット」左シフト演算を実行します。次に、結果の値とビット値の OR が計算されます。

• ステップ 6

  -インデックス 1 から M までのビットセットの値を出力します。

  ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー
単一の for ループを使用するため、時間計算量 - O(N)。

• ビットセットの値を保存するため、空間複雑度 - O(N)。 ＃＃＃結論は＃＃＃

  ここでは、空間と時間の複雑さの点で最初の方法よりも優れた 2 番目の方法を最適化しました。ただし、2 番目の方法は、ビット セットを理解していないと初心者にとっては理解しにくいかもしれません。

以上が指定された条件に従って配列から長さ K のバイナリ文字列を構築しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。