笔试碰到的一道题，求大神解答

const int MAX=500; bool dp[MAX+1][MAX+1]; void beibao(int weight){ for(int i=MAX;i>=0;--i){ for(int j=MAX;j>=0;--j){ if(i>=weight&&dp[i-weight][j]){ dp[i][j]=true; } if(j>=weight&&dp[i][j-weight]){ dp[i][j]=true; } } } } int getNum(int* a,int n){ memset(dp,false,sizeof(dp)); dp[0][0]=true; for(int i=0;i<n;++i) beibao(a[i]); for(int i=MAX;i>=0;--i) if(dp[i][i]) return i; } 早上想了一下，感觉可以用二重背包来写，要注意状态转移要从更大的状态开始操作，细节可参考上述代码。 复杂度为O(n*m^2)  n最大为50，m最大为500。

貌似可以归为动态规划问题？ 谷歌一下how to devide array into two equal parts

我感觉，首先求数组和sum，然后i从sum/2开始遍历到1，再数组中找和为i的子数组，看看是否存在两个不相交的子数组，存在直接返回即可。

    想不到特别好的思路，dfs枚举所有a的子集aa，使得a-aa能拆分成2个和相同的数组（背包）。     然后需要很好的剪枝方法。。。

_huang的思路应该可以，dp(i,j)表示截止到j和为i是否可能，然后遍历从sum/2,到1复杂度应该是50*500*500

f(a,b,i)=f(a,b,i-1)+f(a-n[i],b,i-1)+f(a,b-n[i],i-1)迭代，上限剪枝