このような数値の配列がいくつかあります（配列の各要素は0または1の値のみを取ることができます）
v1: 1; 0; 0; 1; 1; v2: 0; 1; 0; 0; 1; v3: 1; 1; 0; 1; 0; v4: 1; 0; 0; 1; 0; v5: 1; 1; 0; 1; 1; v6: 1; 1; 0; 1; 1;
配列を合計したときに、結果の配列に 2 の倍数である個々の要素が含まれるようなサブセットを見つけたいと考えています。結果の配列は、2 の倍数である任意の値を持つことができます。
もう一つの例：
v1: 1、1、1、0、1、0 v2: 0、0、1、0、0、0 v3: 1、0、0、0、0、0 v4: 0、0、0、1、0、0 v5: 1、1、0、0、1、0 v6: 0、0、1、1、0、0 v7: 1、0、1、1、0、0
この例では、v1+v2+v5 と v3+v6+v7 が適切な回答です。
力ずくの解決策を念頭に置いていますが、より効率的な方法があるかどうかを確認したかったのです。これは部分和問題と同じですか?
すべてのソリューションを検索しますか、それとも 1 つだけを検索しますか?
これで 1 つの解を見つけることができます (すべての解を見つけるように拡張することも可能だと思います)。
各配列を 2 進数で表します。
したがって、v1 は 10011 になり、v2 は 01001 になります。
* はビットごとの mod 2 加算を表します。
例えば
v1*v2*v3 = 00000
したがって、私たちの目的は、mod 2 の加算がすべてゼロである配列を見つけることです。u と v を任意の 2 進数とします。その場合、u = v の場合は u*v = 0 です。
例えば
(v1*v2)*v3 = 0
v1*v2 = 11010 = v3.
また、u*v = w の場合
u*v*v = w*v, so
u*0 = w*v,
u = w*v
したがって、0 から始まる逆方向検索を行うことができます。配列の最終セットに v が含まれているとします。その場合、v*T = 0 となります。ここで、T は 2 進数です。T = 0*v です。T が指定された配列の 1 つである場合、完了です。それ以外の場合は、T から検索を続けます。
これについては、以下で正式に説明します。
各状態は 2 進数です。
0 を初期状態とします。
与えられた配列は、状態空間のサブセット、たとえば S です。
私たちの目標状態は、S の任意の要素です。
T を、合計が 0 である必要な配列のサブセットとします。
各状態で可能なアクションを * とし、T にない状態を指定します。
各アクションの後、T で使用される配列を置きます。
ゴール以外のステージで S = T の場合、解はありません。
これで、この領域で DFS を実行して解決策を見つけることができます。