サブセットサムをパーティションに削減します

Question

Subset-Sum： 数字のリストが与えられていると、空だったサブリストが合計0にあるかどうかを見つけます（0ではなくsum = kが必要なバリエーションがありますが、分析には0が簡単です）

パーティション： リストが与えられれば、それは等しい合計で2人の空でないサブリストに分割することができますか？

Subset-Sumをパーティションに減らしたいと思います。私がこれまでに見つけた削減は同じです これです しかし、それは次の欠点があります：

1. $ b = 0 $の場合、いつでも$ l '$に$ {2s-0 } $、$ {s+0 } ul $に分割できます。
2. $ 2SB $と$ s+b $が異なるパーティションに移動する必要があると想定しています！それらの両方を同じパーティションに入れて、$ -s $に合計する要素、したがって、必要に応じて合計合計$ = 2s $を使用できます。

Answer 1

1. このパーティションが常に発生することは絶対に正しいです。これが対応するサブセットの観点から何を意味するかを考えると、これは空のセット（常にサブセットである）が合計0にあることを示していることがわかります。ターゲットは0で、これはまさに予想通りです。ターゲット合計を0に修正すると、問題が議論されやすくなるだけでなく、複雑さの意味で容易になります（$ o（1）$はイエスをすぐに出力します）。

2. あなたもここにいます。入力が正の整数のリストであるサブセット合計の定式化があり、あなたが読んでいる削減はその言語からだったと思います。目標は、追加の要素を同じ大きさにすることで、両方が同じ部分に行くことができないことでした。パッチを当てるために、絶対値の合計を使用できます。これは実際には、2S $ $ $が実際に$ s +$ some-large-number-for-for-$ s $ s $ s $ -will-suffice-so-do-larger-だったため、実際に証明の構造の一部をよりよく示しています。数字。

この時点で、私はリンクされた投稿からコピーして、ネガを処理するために編集するだけです。

$（l、b）$をサブセット合計のインスタンスとします。ここで、$ l $は数字のリスト（マルチセット）、$ b $はターゲット合計です。 $ s = sum l $と$ s '> sum_ {l in l} | l | $を選択します。 $ l '+を$ s'+b、s '+sb $〜$ l $を追加することにより形成されたリストとします。

（1）サブリスト$ m subseteq l $が$ b $に合計されている場合、$ l '$は2つの等しい部分に分割できます：$ m cup {s' + sb } $および$ l setMinus m cup {s '+b } $。実際、最初の部分は$ b+（s '+sb）= s'+s $に合計し、2番目は$（sb）+（s '+b）= s'+s $になります。

（2）$ l '$を2つの等しい部分$ p_1、p_2 $に分割できる場合、$ l $のサブリストが$ b $になります。 2つの新しい要素の合計は$（s '+b）+（s'+sb）= 2s '+s $です。すべてのサブセット$ a Subset l $は$ left | sum a right | <s '$、したがって、$ {s'+sb } cup {s '+b } cup a $がsum $ s'+s $を持っていることは不可能です（常に大きい）。したがって、2つの新しい要素は異なる部分に属します。一般性を失うことなく、$ s '+sb in p_1 $。 $ p_1 $の残りの要素は$ l $に属し、合計$ b $に属します。新しい要素は含まれていないため、サブセット合計の解決策です。