2

負でない整数のリストが与えられた場合、リストNの数値の合計がX残りの と等しいかどうかをチェックするアルゴリズムを提案しますN-X。

言い換えれば、集合全体を含む部分和問題のより単純なケースです。

試みられた解決策

リストの要素を降順に並べ替えます。変数SUMを最初の要素に初期化します。最初の要素 (最大、 ) を削除しa(1)ます。現在のリストの要素を示すa(n)ようにします。n-th

リストには複数の要素がありますが、

  1. またはのいずれか最も近いものに等しくSUMします。(最も近い平均が最小である場合)。SUM + a(1)SUM - a(1)a(2)|a(2) - SUM_POSSIBLE|

  2. を削除しa(1)ます。

がまたはにSUM等しい場合、線形和が存在します。-a(1)a(1)

問題

上記のアルゴリズムを解決できないようです。正しい場合は、証明が必要です。それが間違っている場合 (より可能性が高い)、線形時間でこれを行う方法はありますか?

PS: 私が何か間違ったことをしているなら、許してください:S

4

1 に答える 1

1

x数値の合計を他の数値の合計と等しくする必要があることに注意してくださいN-x。これを単純化するには、合計がセット全体の合計で
あるサブセットがあるかどうかを確認する必要があります。S/2S

したがって、1回の反復で取得する必要のある合計を計算できます（O（n））。

次に、Knapsackなどの既知のアルゴリズムを使用して、合計に一致するサブセットを見つけます。

もう1つの「数学的な」説明：動的計画法– 3：サブセット和

編集：

あなたの他の質問への答えとして、あなたのアルゴリズムは間違っています。この番号のリストを検討してください。

{3,3,4,4}

合計は14なので、合計が7のサブセットを探しています。明らかに3+4になります。

2 3を調べた後、アルゴリズムはfalseを返します

于 2012-07-29T06:40:53.040 に答える