Comment puis-je réduire la somme à la partition Sous-ensemble?
https://cs.stackexchange.com/questions/6111
-
16-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
La solution
Soit $ (L, B) $ soit une instance de somme sous-ensemble, où $ L $ est une liste (multiset) des numéros, et $ B $ est la somme cible. Soit $ S = \ somme L $. Soit $ L '$ soit la liste formée en ajoutant $ S + B, $ 2S-B à $ L $.
(1) S'il y a une sous-liste M $ de subseteq L de $ la somme de $ B $, puis $ L 'peut être partitionné $ en deux parties égales: la coupe M $ \ {2S-B \} $ et $ L \ setminus tasse M \ {S + B \} de $. En effet, les premières sommes partielles à $ B + (2S-B) = 2S $, et le second à $ (S-B) + (S + B) = 2S $.
(2) Si $ L '$ peut être divisée en deux parties égales p_1 $, P_2 $, alors il y a une sous-liste de $ L $ somme à $ B $. En effet, depuis $ (S + B) + (2S-B) = 3S $ et la somme de chaque partie à $ 2S $, les deux éléments appartiennent à différentes parties. Sans perte de généralité, $ 2S-B \ en P 1 $. Le reste des éléments de $ $ P 1 appartiennent à $ L $ et la somme de $ B $.
Autres conseils
La réponse mentionnée par @Yuval Filmus est incorrect (il est correcte seulement s'il n'y a pas de nombres entiers négatifs ). Considérons le multiset suivant:
$$ \ {- 5, 2, 2, 2, 2, 2 \} $$
et la somme cible est $ -2 $. Nous savons qu'il n'y a pas sous-ensemble. Maintenant, nous construisons l'instance pour le problème de la partition. Les deux nouveaux éléments sont ajoutés 2 $ \ sigma-t = $ 12 et $ \ sigma + t = 3 $. Le multiset est maintenant: $$ \. {- 5, 2, 2, 2, 2, 2, 3, 12 \} $$ et la somme totale est de 20 $ $
Le problème de partition résout la réponse donnant le sous-ensemble $$ \ {2, 2, 2, 2, 2 \} $$ Ici, les 2 nouveaux éléments sont dans le même sous-ensemble (il n'y a pas d'autre moyen de partition dans la moitié la somme). Par conséquent, c'est un contre-exemple. La bonne réponse est la suivante:
Ajouter un élément dont la valeur est $ 2T \ sigma $. La somme totale de la multiset est maintenant $ 2t $. Résoudre le problème de la partition qui donnera 2 sous-ensembles de somme $ t $. Une seule de la partition contiendra le nouvel élément. Nous choisissons l'autre partition dont la somme est de $ t $ et nous avons résolu le problème du sous-ensemble en réduisant dans un problème de partition. C'est ce que le lien explique.
Voici une preuve directe:
Il est facile de voir que SET-PARTITION peut être vérifiée en temps polynomial; étant donné une partition $ P 1, P_2 $ somme que les deux et vérifier que leurs montants égaux les uns des autres, ce qui est évidemment une vérification en temps polynomiale (parce que la sommation est une opération polynomiale et nous n'accomplissons au plus $ | X | $ beaucoup de sommations).
Le noyau de la preuve est dans la réduction de SubsetSum PARTITION; à cette fin, compte tenu ensemble $ X $ et une valeur $ t $ (la somme des sous-requêtes) on forme une nouvelle série $ X '= X \ cup \ {s-2t \} $ où $ s = \ sum_ {x \ X} x $ . Pour voir que cela est une réduction:
-
( $ \ implique $ ) Supposons qu'il existe une $ S \ subset X $ de telle sorte que $ t = \ sum_ {x \ in S} x $ nous aurions que \ begin {equation *} s-t = \ sum_ {x \ in S \ cup \ {s-2t \ x}}, \ End {equation *} \ begin {equation *} s-t = \ sum_ {x \ in X » \ setminus (S de la coupelle \ {s-2t \})} x \ End {equation *} et nous aurions que tasse de $ S \ {s-2t \} $ et $ X » \ setminus (S \ cup \ {s-2t \}) ??$ former une partition de $ X '$
-
( $ \ impliedby $ ) On suppose qu'il y a une partition $ P_1' , P_2' $ $ X '$ tels que $ \ sum_ {x \ in P 1'} x = \ sum_ {x \ dans P_2' } x $ . Notez que ce qui induit une partition naturelle $ P_1 $ et $ P_2 $ $ X $ de telle sorte que nous avons WLOG que \ begin {equation *} s-2t + \ {x sum_ \} dans P 1 x = \ {x sum_ \ in P_2} x \ End {equation *} \ begin {equation *} \ Implique l-2t + \ {x sum_ \ in} x P 1 + \ {x sum_ \} dans P 1 x = \ {x sum_ \ in P_2} x + \ {x sum_ \ dans} x = P 1 s \ End {equation *} \ begin {equation *} \ Implique l-2t + 2 \ {x sum_ \ dans} x = P 1 s \ End {equation *} \ begin {equation *} \ Implique \ {x sum_ \} dans P_1 x = t \ End {equation *}
Par conséquent d'une solution $ t = \ sum_ {x \ in S} x $ nous pouvons former une parition $ P 1 = s de tasse \ {s-2t \} $ $ P_2 = X » \ setminus (s \ cup \ {s-2t \}) ??$ et inversement à partir d'une partition $ P 1' , P_2' $ nous pouvons former une soltuion $ t = \ sum_ {x \ in P 1 '\ setminus \ {s-2t \}} x $ et donc la cartographie $ f: (X, t) \ rightarrow X' $ est une réduction (parce que $ (X, t) $ est dans la langue / set SubsetSum $ \ leftrightarrow X '= f (x, t) $ est dans la partition de langue / set) et il est clair pour voir que la transformation a été effectuée en temps polynomial.
Somme Subset:
Entrée: {a1, a2, ..., am} S.T M = {} 1..m et ai sont des nombres entiers non négatifs de et S? {} et 1..K Sai (i?S) = t
Partition:
Entrée: {a1, a2, ..., am} et S? {1, · · ·, m} S.T Sai (i?S) = Saj (j?S)
Partition Np Preuve: si prouveur fournit une partition (P1, P2) pour vérification, peut facilement calculer la somme de vérification P1 et P2 et vérifier si le résultat est égal à 0 dans le temps linéaire.
NP_Hard: SubsetSum PARTITION = p
Soit x entrée de SubsetSum et x =
Cas1: 2t> = a:
Soit f (x) =
Nous voulons montrer que x?SubsetSum ? f (x) ?PARTITION
de sorte qu'il existe S? {1, ..., m} S.T T = {} 1..m - S et Sai (i?T) = a-t
et soit T '= {1 ... m, m + 1} - S si Saj (j?T') = a-t + 2t-a = t
qui est exactement Sai (i?S) = t et il montre f (x) ?PARTITION
Nous allons maintenant aussi montrer que f (x) ?PARTITION ? x?SubsetSum
donc il existe S? {1, ..., m, m + 1} st T = {1, ..., m, m + 1} - S et Sai (i?T) = [a + ( 2t-a) -t] = t
et il montre Sai (i?T) = Saj (j?S) si m + 1?T et S? {1, · · ·, m} et Sai (i?S) = t
x?SubsetSum
Cas n ° 2: 2t = :
nous pouvons vérifier même mais juste cette fois-am + 1 est un 2t
