la réduction de sous-ensemble d'une somme de partition

Question

Sous-ensemble somme: Compte tenu de la liste des numéros, trouver si une sous-liste non vide a somme 0 (il y a une variation où nous voulons somme = k au lieu de 0, mais 0 est plus facile pour l'analyse )

Partition: Compte tenu de la liste, il peut être divisé en deux sous-listes non vides avec somme égale

Je veux réduire somme sous-ensemble à la partition. Les réductions que j'ai trouvé à ce jour sont les mêmes que celui-ci mais il a des défauts suivants:

1. Pour $ B = 0 $, vous pouvez toujours partitionner $ L '$ en $ \ {2S-0 \} $, $ \ {S + 0 \} U L $.
2. Il suppose $ 2S-B $ et $ S + B $ doivent aller à différentes partitions! Vous pourriez avoir les deux dans la même partition avec des éléments qui somme -S $ $, somme donc au total $ = 2S $ au besoin.

Answer 1

1. Vous avez tout à fait raison de dire que cette partition se produit toujours. Si l'on considère ce que cela signifie en termes de sous-ensemble correspondant, vous verrez que cela indique que l'ensemble vide (ce qui est toujours un sous-ensemble) a somme 0. En fait, cela signifie que l'il y a toujours une solution à somme sous-ensemble lorsque la cible est égal à 0, ce qui est exactement comme prévu. Il se trouve fixer la somme cible à 0 ne se contente pas rendre le problème plus facile de discuter, il est plus facile dans un sens de la complexité (O $ (1) $ par sortie OUI immédiatement).

2. Vous avez raison ici aussi. Il y a une formulation de somme sous-ensemble où l'entrée est une liste d'entiers positifs, et je pense que la réduction que vous lisez est de cette langue. L'objectif était d'avoir nos éléments ajoutés soient assez grands qu'ils ne peuvent pas aller à la fois dans la même partie. Pour patch, nous pouvons utiliser la somme des valeurs absolues. Cela montre en fait une partie de la structure de la preuve mieux, parce que $ 2S $ était en fait $ S + $ marre-numéro-grand-pour-which- $ S $ -Est-mais-suffire-soi-do-larger- numéros.

A ce point, je suis copier-coller à partir du poste lié et l'édition juste négatifs manche:

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 $ et choisissez $ S »> \ {sum_ l \ in L} | l | $. Soit $ L '$ soit la liste formée en ajoutant $ S' + B, S '+ S-B $ à $ L $.

(1) S'il y a une sous-liste M $ de subseteq L de $ la somme de $ B $, puis $ L '$ peut être divisée en deux parties égales: $ M \ cup \ {S' + SB \} $ et $ L \ setminus M tasse \ {S '+ B \} $. En effet, les premières sommes partielles à $ B + (S '+ S-B) = S' + S $, et le second à $ (S-B) + (S '+ B) = S' + S $.

(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 $. La somme des deux nouveaux éléments est $ (S '+ B) + (S' + S-B) = 2S + 'S $. Tous les sous-ensembles $ A \ subset L $ ont $ \ left | \ somme A \ right |