通过将一个集合划分为两个子集，找出可以形成的最大和

本文介绍了通过将一个集合划分为两个子集，找出可以形成的最大和的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给出一组数字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