给出一组数字S.求最大和Sum(A 1 )= Sum(A 2 )其中,A 1 ⊂ S和A 2 ⊂ S和A 1 ⋂A 2 =∅Sum(X)是集合X中所有元素的总和.
Given a set of numbers S. Find maximum sum such that Sum(A1) = Sum(A2) Where, A1⊂S and A2⊂S and A1⋂A2=∅ And Sum(X), is the sum of all elements within the set X.
蛮力
最简单的方法是:
print maximumSum(0,0,0) def maximumSum(index,sum1,sum2): ans=0 if sum1 == sum2: ans=sum1 if index >= len(S): return ans m1=maximumSum(index+1,sum1+S[index],sum2) m2=maximumSum(index+1,sum1,sum2+S[index]) m3=maximumSum(index+1,sum1,sum2) return max(m,m1,m2,m3)时间复杂度:O(2 N )空间复杂度:O(1)
Time Complexity:O(2N)Space Complexity:O(1)
有没有比这更好的方法了?可选:我想知道给定的问题是否是NP完全问题.
Is there a better approach than this? Optional: I would like to know whether the given problem is an NP-Complete problem or not.
1< =总和(S)< = 1000000 2< = len(S)< = 100 时间限制:60秒(可能会因使用的语言而异)
1 <= Sum(S) <= 1000000 2 <= len(S) <= 100 Time Limit: 60sec(can vary depending upon language used)
推荐答案是,这是NPC问题分区问题
如果集合的总和很小,您可以看到伪多项式算法部分
You can see the pseudo polynomial algorithm part if the sum of the set is small
更多推荐
通过将一个集合划分为两个子集,找出可以形成的最大和
发布评论