Apakah Subset Sum memperbolehkan multiset?

Dalam masalah Subset Sum, bisakah beberapa angka yang diberikan sama? Sebagai contoh, kita mungkin memiliki dan targetnya adalah ? Dapatkah saya berasumsi bahwa saya memiliki solusi spesifik dengan angka dan dan dan tidak? $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 ingin tahu
sumber

Anda mengatakan potayto, saya katakan potahto. Sangat umum bagi para ilmuwan komputer untuk mengaburkan perbedaan formal antara set dan multiset; satu-satunya cara untuk memastikan adalah membaca definisi dengan hati-hati . Semua varian dari masalah Jumlah Subset adalah NP-complete.

JeffE

Jawaban:

Satu pertanyaan yang bisa kami tanyakan adalah "Bisakah kita mengurangi ini kembali ke masalah jumlah subset?" Dalam hal ini, jawabannya adalah ya : untuk setiap duplikat kami menggantinya dengan dua angka dan sedemikian rupa sehingga . $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]$

Namun, kita perlu berhati-hati bahwa kita tidak memperkenalkan solusi tambahan (yang hanya menggunakan tanpa ), yang dapat kita lakukan dengan membuat untuk , dan untuk . Secara khusus, ini menghalangi penggunaan tanpa (dan sebaliknya) dengan membuat jumlah dan semua angka negatif benar-benar di atas nol (dan dengan demikian tidak memenuhi masalah jumlah subset tradisional). $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
sumber