Sous-ensemble: réduire le cas spécial au cas général

Wikipedia indique que le problème de la somme des sous-ensembles consiste à trouver un sous-ensemble d'un multiset donné d'entiers, dont la somme est nulle. De plus, il déclare qu'il revient à trouver un sous-ensemble avec la somme $s$ pour tout $s$ donné .

Je pense donc que comme ils sont équivalents, il doit y avoir une réduction de chaque côté. Celui de $s$ à zéro est trivial en mettant $s = 0$ . Mais je n'ai pas eu de chance de trouver une réduction de zéro à $s$ , c'est-à-dire étant donné un ensemble d'entiers $A$ , construire un ensemble d'entiers $B$ contenant un sous-ensemble avec la somme $s$ (pour tout $s$ ), si et seulement s'il y a comme sous-ensemble de $A$ avec somme zéro.

Pouvez-vous me donner quelques conseils?

En fait, vous avez déjà une réduction de spécial à général. En définissant $s=0$ , vous utilisez essentiellement l'algorithme général pour résoudre le problème spécial.

Pour l'inverse (c'est-à-dire une réduction du général au spécial):

Supposons que vous êtes donné un ensemble $S = \{x_1, \dots, x_n\}$ et un nombre $K$ et vous devez déterminer s'il y a un sous - ensemble de $S$ qui sommes à $K$ .

Maintenant, vous voulez résoudre ce problème, étant donné un algorithme pour le cas où vous pouvez déterminer si certains sous-ensembles totalisent $0$ .

Or si $x_i \gt 0$ , on a une réduction facile: $S' = \{x_1, x_2, \dots, x_n, -K\}$ .

a un sousensemble de somme 0 iff S disposeun sousensemble de somme K .$S'$$0$$S$$K$

Le problème se produit lorsque nous pouvons avoir pour certains des i .$x_i \le 0$$i$

Nous pouvons supposer que (pourquoi?).$K \gt 0$

Supposons que la somme des valeurs positives est P et le négatif ix i est N .$x_i$$P$$x_i$$N$

Construisons maintenant un nouvel ensemble tel que$S' = \{y_1, y_2 \dots, y_n\}$

où M = P + | N | + K .$y_i = x_i + M$$M = P + |N| + K$

Chaque .$y_i \gt 0$

Exécutez maintenant l'algorithme de somme de sous-ensemble zéro sur les ensembles

$S' \cup \{-(K+M)\}$

$S' \cup \{-(K+2M)\}$

$S' \cup \{-(K+3M)\}$

$\dots$

$S' \cup \{-(K+nM)\}$

Il est facile de montrer que si a un sous-ensemble de somme K , alors au moins l'un des ensembles ci-dessus a un sous-ensemble de somme zéro.$S$$K$

Je vous laisse la preuve de l'autre sens.

La réponse d'Aryabhata peut être corrigée en utilisant le fait que nous pouvons multiplier tous les nombres par un grand $c$ , puis ajouter quelque chose de petit à chacun pour agir comme une "balise de présence", puis fournir des nombres supplémentaires qui permettront nous pour arriver à zéro si nous pouvions arriver à $cK$ sans eux. Plus précisément, nous utiliserons $c=2(n+1)$ et 1 comme balise de présence.

Étant donné une instance $(S = \{x_1, \dots, x_n\}, K)$ du problème général avec la valeur cible $K$ , nous allons créer une instance du problème spécifique (avec la valeur cible 0) qui contient:

• $Y = \{y_1, \dots, y_n\}$ , où$y_i = 2(n+1)x_i + 1$ .
• Le nombre $z = -2K(n+1)-n$ .
• $n-1$ exemplaires du numéro 1, appelés numéros "pull-up".

Je suppose qu'Aryabhatta fait que $K$ est positif. (Comme cela fait 6 ans, je répondrai à son exercice pour le lecteur: la raison pour laquelle nous pouvons le faire est que si nous échangeons les signes de tous les nombres dans une instance du problème général, y compris $K$ , nous nous retrouvons avec un nouvelle instance de problème équivalente. Cela signifie qu'un algorithme pour résoudre des instances $K$ positives suffit à résoudre n'importe quel problème - pour résoudre une instance avec $K$ négatif , nous pourrions effectuer cet échange de signe, exécuter cet algorithme et transmettre sa réponse en tant que la réponse à la question d'origine. Et bien sûr, si $K=0$ alors nous n'avons pas du tout besoin de transformer le cas général en cas spécial!)

Montrons d'abord qu'une réponse OUI à l'instance donnée du problème général implique une réponse OUI à l'instance construite du problème spécial. Ici , nous pouvons supposer que une solution $\{x_{j_1}, \dots, x_{j_m}\}$ au problème général existe: qui est, cette collection non vide de $m$ nombres sommes à $K$ . Donc, si nous prenons les valeurs $y$ correspondantes $\{y_{j_1}, \dots, y_{j_m}\}$ dans notre solution à l'instance construite, elles totaliseront $2K(n+1)+m$ . On peut alors choisir d'inclure$-2K(n+1)-n$ dans la solution, ce qui nous laisse une somme de$m-n$ . Puisque$1 \le m \le n$ , ceci dans la gamme$[-n+1, 0]$ , que nous pouvons réussir à tirer jusqu'à 0 en incluant un sous-ensemble des nombres de pull-up.

Montrons maintenant qu'une réponse OUI à l'instance construite implique une réponse OUI à l'instance donnée d'origine. C'est là que la multiplication par $2(n+1)$ devient importante - c'est ce qui nous permet d'être certains que les nombres supplémentaires que nous avons inclus ne peuvent pas "faire trop".

Ici, nous pouvons supposer qu'il existe une solution $\{y_{j'_1}, \dots, y_{j'_{m'}}\}$ à l'instance construite: c'est-à-dire que cette collection non vide de $m'$ égale à 0. Par les exigences du problème, cette solution contient à au moins un élément. De plus, il doit contenir au moins un élément de $Y$ , car sans cela, il est impossible d'atteindre un total de 0: si seuls des nombres de pull-up sont présents, alors la somme est nécessairement dans la plage $[1, n-1]$ ( notez que dans ce cas au moins unle nombre de pull-up doit être présent, et tous sont strictement positifs, donc la somme ne peut pas être 0); alors que si la solution se compose uniquement de $z$ et de quelques nombres de pull-up, alors le total est nécessairement négatif parce que $z = -2K(n+1)-n \le -n$ et le plus que les nombres de pull-up peuvent augmenter la somme par est $n-1$ .

Now suppose towards contradiction that the solution does not contain $z$. Every element in $Y$ consists of two terms: A multiple of $2(n+1)$, and a +1 "presence tag". Notice that the +1 term on each of the $n$ elements of $Y$ increases the sum by 1 if that element is chosen, as does each of the up to $n-1$ pull-up numbers that are chosen, so the total contributed by these 2 sources to any solution is at least 1 (because we established in the previous paragraph that at least one element of $Y$ must be chosen) and at most $n + n-1 = 2n-1$. In particular, this implies that the sum of these two sets of terms, when taken modulo $2(n+1)$, is nonzero. Under the assumption that the solution does not contain $z$, the only other components in this sum are the multiples of $2(n+1)$ contributed by the chosen members of $Y$, which do not affect the value of the sum when taken modulo $2(n+1)$. Thus the sum of all terms in the solution, when taken modulo $2(n+1)$, is nonzero, meaning it cannot be equal to the target sum of 0, meaning it cannot be a valid solution at all: we have found a contradiction, meaning that it must be that $z = -2K(n+1)-n$ is present in every solution after all.

So every solution contains $z$. We know that

$(-2K(n+1) - n) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}} + 1) + \sum {\text{pull-ups}} = 0$,

and we can rearrange the terms:

$-2K(n+1) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}}) - (n + \sum_{i'=1}^{m'} 1 + \sum {\text{pull-ups}}) = 0$

$-2K(n+1) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}}) - (n + m' + \sum {\text{pull-ups}}) = 0$

$2(n+1)(-K + \sum_{i'=1}^{m'} x_{j'_{i'}}) - (n + m' + \sum {\text{pull-ups}}) = 0$.

Since the sum is 0, it must remain 0 when taken modulo $2(n+1)$, which implies that we can discard all terms containing a multiple of $2(n+1)$ to obtain the new equation

$-(n + m' + \sum {\text{pull-ups}}) = 0$.

This can be directly substituted back into the previous equation to get

$2(n+1)(-K + \sum_{i'=1}^{m'} x_{j'_{i'}}) = 0$.

Finally, dividing both sides by $2(n+1)$ leaves

$-K + \sum_{i'=1}^{m'} x_{j'_{i'}} = 0$,

which yields a solution to the original general problem instance.