Le sous-ensemble Sum autorise-t-il les multisets?

Dans le problème de sous-ensemble, certains des nombres donnés peuvent-ils être les mêmes? Par exemple, nous pourrions avoir et l'objectif est de ? Puis-je supposer que j'ai une solution spécifique avec les numéros et et et ne l'est pas? $a_1,a_2,a_3,\dots,a_n$ $[1,1,1,2,3,4]$ $5$ $2$ $3$ $1,1,1$ $2$

complexity-theory terminology curieuse
la source

Vous dites potayto, je dis potahto. Il est assez courant pour les informaticiens de brouiller la distinction formelle entre les ensembles et les multi-ensembles; la seule façon d'en être sûr est de lire attentivement la définition . Toutes les variantes du problème Subset Sum sont NP-complete.

JeffE

Réponses:

Une question que nous pourrions poser est "Pouvons-nous réduire cela au problème de somme de sous-ensemble?" Dans ce cas, la réponse est oui : pour chaque dupliqué, nous le remplaçons par deux nombres et tels que . $z$ $x$ $y$ $x+y=z$

[- 1, - 1, 2, 3] \to [- 7, - 1, 2, 3, 6]

$[-1,-1,2,3]\to [-7,-1,2,3,6]$

Cependant, nous devons faire attention à ne pas introduire de solutions supplémentaires (celles utilisant juste sans ), ce que nous pouvons faire en faisant pour , et pour . Plus précisément, cela empêche l'utilisation de sans (et vice versa) en rendant la somme de et de tous les nombres négatifs strictement supérieure à zéro (et ne satisfait donc pas le problème de somme de sous-ensemble traditionnel). $x$ $y$ $x>\lvert \Sigma(a_i)\rvert$ $a_i<0\in A$ $y<-\lvert\Sigma(a_i)\rvert$ $a_i>0 \in A$ $x$ $y$ $x$

Merbs
la source