首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

关于NP完全的有关问题。实在弄不明白这个东西。

2012-02-09 
关于NP完全的问题。。实在弄不明白这个东西。。给定一个数组S, 这个数组能不能被分成两个数组A和B,使得数组A和

关于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的答案)

热点排行