数组的最大划分

wayne

给定一个正整数序列 S，序列长度Length(S) ≤50，序列之和Total(S)≤1000.  
求助: 如何从中提取两不交子列A, B，使得Total(A)=Total(B):=T？只需输出Tmax, 如果只有A=B=φ(空集), 则Tmax=0.
限定程序运行时间 5s 内, 内存占用 64M .

zeroieme

我遇过类似的问题，序列长度过万。用贪婪法加交换纠正。
感觉长序列更容易获得两个等和子列。

--------------
这里如果总和为奇数，就剔除序列中的最小奇数。

wayne

zeroieme 发表于 2017-6-3 22:55
我遇过类似的问题，序列长度过万。用贪婪法加交换纠正。
感觉长序列更容易获得两个等和子列。

贪婪的话，效率能跟得上吗

zeroieme

wayne 发表于 2017-6-4 17:29
贪婪的话，效率能跟得上吗

作为初始结果，贪婪是最快的。只是线性。
后面一步交换纠正要看你的计算环境能有多少资源。

mathe

所有元素之和为偶数，那么判断是否存在一半元素和正好是总和一半的算法可以通过动态规划来做。然后可以试着在整个数字中去掉少量元素使得余下和为偶数判断是否存在前面的划分。在存在划分使用大部分元素的情况下可以很快找到解

wayne

这是我遇到的一道笔试上机题. 限定程序运行时间是$5s$, 我 当时是用 C++做的, 没留意到 OJ 虽然支持C++提交, 提交却 不支持C++的  vector 和map, 搞的比较糟糕, 没有真正的算法试错环节,没通过.

zeroieme

wayne 发表于 2017-6-5 09:33
这是我遇到的一道笔试上机题. 限定程序运行时间是$5s$, 我 当时是用 C++做的, 没留意到 OJ 虽然支持C++提交 ...

哦，我还以为是实际问题的子问题。需要限制储存量之类的。

mathe

是不是要求A,B元素数目相同而且元素和也相同？
解是否存在的判断可以直接用动态规划判断。
我们设C(n,s)为n个元素和为s的方案数目，使用动态规划就可以求出所有的C(n,s).
显然如果所有的C(n,s)都是0或1，那么就无解，如果任意的C(n,s)大于1，就说明存在两组不同的长度为n的子数列，它们的和都是s,去掉公共元素，就得出两个不相交A,B元素数目和元素和都相同。