Re: question on variation of subset sum problem

On Mar 27, 9:33 pm, "amandeep.par...@xxxxxxxxx"
<amandeep.par...@xxxxxxxxx> wrote:
Hi,

The problem I have is a variation of subset sum. Given $n$ numbers
a_1, a_2 , ..., a_n and b. Does there exists sets S_1 and S_2
disjoint, subsets of {1,2,...,n} such that

Sum_{i in S_1} a_i + 1/2 Sum_{i in S_2} a_i = b ?

I think this is a NP-complete problem but I cant seem to show it. Any
comments would be greatly appreciated. Thanks,

-aman

Put another extra element in to the set S of n numbers = 2*Sum_{i in
S}a_i = 2X (suppose).
Reduce subset sum problem with sum b to this problem with k = X + b.

Thanks.

--- Pinaki

====================================================================

.