关于NP完全的问题。。实在弄不明白这个东西。。
给定一个数组S, 这个数组能不能被分成两个数组A和B,使得数组A和数组B内的数字总和相等。
证明这个问题是NP完全问题。。。
HINT:先证明这个问题是NP,然后用subset-sum来reduce这个问题。。
[解决办法]
假设楼主这个数组S的数据和为sum,元素为s0,s1,s2,s3,...sn。
解决了SUBSET-SUM问题的就能解决楼主的问题,问题描述为:
“有一个数集S(数组S),是否包含和为sum/2的子集?”
解决了楼主的问题的就能解决SUBSET-SUM问题,问题描述为:
“有一个数组S(s0,s1,s2,s3,...,sn, -s0,-s1,-s2,-s3,...,-sn+2*N,),
能不能被分成两个数组A和B,使得数组A和数组B内的数字总和相等(明显=N)”
如果能分成,则SUBSET-SUM{(s0,s1,s2,s3,...,sn)(N)}问题可解。
(分成的两组有一组不含-sn+2*N,另外一组正负抵消后就是和为N的答案)