この問題は NPC の目視検査によって解決されます。それは「2つのステップ」に分けられます。

1. すべての「追加のサブセット」を検索します。各要素を可能な合計として取得し、サブセット合計アルゴリズムを使用して 1 つずつ解決します。

2. 相互に排他的な加法サブセットの最大和集合を見つけます。セット パッキング アルゴリズムを参照し、線形計画法を使用してそれを解決します。

以下では、Mathematica を使用してアルゴリズムを詳細に説明します。

追加サブセットを検索

セット内の加算式を構成するすべての数値を列挙するには (負の数値と繰り返しの数値を許可)、まずサブセット合計アルゴリズム (キャッシュによる再帰) を使用して、合計が指定された数値となるサブセットを列挙します。

コードは q を再帰的に呼び出し、結果をキャッシュします。特定の再帰的導出については、この質問を参照してください。計算された追加サブセットは内部で並べ替えられ、最後に重複を削除するために結合演算が実行されることに注意してください。使用例:

この問題では、指定された数値はセット内の任意の要素である可能性があるため、subsetSum を使用してセット内の各要素を反復処理し、その要素と残りの要素との加算を作成してみます。最後に、重複する組み合わせが削除され、これが可能な追加サブセットの合計となります。

上記のコードは、セットに対して内部ソート操作も実行します。これは、セットに sum と sum を追加するときに順序が崩れる可能性があるためです。また、加数の数が 2 未満の場合は削除されます。使用例:

相互に排他的な最大和集合を求める

加算サブセットを取得した後、重み付きセット パッキングを使用して、それらの間の相互に排他的な最大和集合を見つけます。線形計画言語で記述すると

$$array{text{maximize} & sum{|s_i| セットは相互に排他的です} \ & x_i in {0, 1} & text{$x_i=1$、次に set $i$ を選択、そうでない場合は set を破棄します$i$}}$$

Mathematica は組み込みの LinearProgramming 関数を提供します:

テスト

トピックの例:

16 個の要素のセットをランダムに生成します。

pickSumList で結果を検索し、合計である要素を強調表示します:

残りの要素: