Erlaubt Subset Sum Multisets?

Können im Teilmengen-Summenproblem einige der angegebenen Zahlen gleich sein? Zum Beispiel könnten wir und das Ziel ist ? Kann ich davon ausgehen, dass ich eine bestimmte Lösung mit den Nummern und und und nicht? $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 neugierig
quelle

Du sagst Potayto, ich sage Potahto. Für Informatiker ist es durchaus üblich, die formale Unterscheidung zwischen Mengen und Multisets zu verwischen. Der einzige Weg, um sicher zu sein, besteht darin , die Definition sorgfältig zu lesen . Alle Varianten des Subset Sum-Problems sind NP-vollständig.

JeffE

Antworten:

$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]$

$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$ und alle negativen Zahlen streng über Null (und erfüllen somit nicht das traditionelle Teilmengen-Summenproblem).

Merbs
quelle