通过将一个集合划分为两个子集，找出可以形成的最大和 [英] Finding the maximum sum that can be formed from a set, by partitioning it into two subset

问题描述

给出一组数字S.
求最大和
Sum(A ₁ )= Sum(A ₂ )
其中，A ₁ ⊂ S和A ₂ ⊂ S和A ₁ ⋂A ₂ =∅
Sum(X)是集合X中所有元素的总和.

Given a set of numbers S.
Find maximum sum such that
Sum(A₁) = Sum(A₂)
Where, A₁⊂S and A₂⊂S and A₁⋂A₂=∅
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(2^N)
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

这篇关于通过将一个集合划分为两个子集，找出可以形成的最大和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！