patternMinor
Negative numbers in Subset-Sum
Viewed 0 times
numberssubsetnegativesum
Problem
If I have a set $A$ with positive and negative numbers, and a number to find C.
It is possible to reduce the problem to one with only positive numbers in set $A$?
I mean, it is possible to find a new set $A$ and a new number $C$, so $A$ were only positive numbers, but the same problem?
It is possible to reduce the problem to one with only positive numbers in set $A$?
I mean, it is possible to find a new set $A$ and a new number $C$, so $A$ were only positive numbers, but the same problem?
Solution
Hint: Let $A = \{ a_1,\ldots,a_n \}$. Choose a large number $M$ and consider the set $\{ M + a_1, \ldots, M + a_n, M, \ldots, M \}$ ($n$ times the number $M$) and the target $nM + C$. If you want an actual set, instead of taking $n$ times the number $M$, take $M,2M,4M,\ldots,2^{\lceil \log_2 n \rceil}M$ (we assume that $0 \notin A$; otherwise, remove $0$ from $A$).
Context
StackExchange Computer Science Q#24050, answer score: 8
Revisions (0)
No revisions yet.