找回密码
 欢迎注册
查看: 6361|回复: 17

[求助] 数组的最大划分

[复制链接]
发表于 2017-6-3 20:38:10 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
给定一个正整数序列 S,序列长度Length(S) ≤50,序列之和Total(S)≤1000.  
求助: 如何从中提取两不交子列A, B,使得Total(A)=Total(B):=T?只需输出Tmax, 如果只有A=B=φ(空集), 则Tmax=0.
限定程序运行时间 5s 内, 内存占用 64M .
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-3 22:55:34 | 显示全部楼层
我遇过类似的问题,序列长度过万。用贪婪法加交换纠正。
感觉长序列更容易获得两个等和子列。

--------------
这里如果总和为奇数,就剔除序列中的最小奇数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-6-4 17:29:34 | 显示全部楼层
zeroieme 发表于 2017-6-3 22:55
我遇过类似的问题,序列长度过万。用贪婪法加交换纠正。
感觉长序列更容易获得两个等和子列。


贪婪的话,效率能跟得上吗
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-4 17:34:06 | 显示全部楼层
wayne 发表于 2017-6-4 17:29
贪婪的话,效率能跟得上吗

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

点评

嗯  发表于 2017-6-5 20:29
我当时的情况是过万个实数,想|A-B|尽量小。这里所有元素之和最多为 1000,还是用动态规划好。  发表于 2017-6-5 10:01
加了限定条件是5s的时间, 你的算法能满足这个要求吗  发表于 2017-6-5 09:29
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-4 20:49:59 来自手机 | 显示全部楼层
所有元素之和为偶数,那么判断是否存在一半元素和正好是总和一半的算法可以通过动态规划来做。然后可以试着在整个数字中去掉少量元素使得余下和为偶数判断是否存在前面的划分。在存在划分使用大部分元素的情况下可以很快找到解

点评

感觉像是一种尝试算法.而非确定输出解的算法方案. 题目要求是 存在解就输出, 不存在也要输出.输出为 -1  发表于 2017-6-5 09:39
对啊动态规划计算量跟元素总和相关  发表于 2017-6-4 21:09
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-6-5 09:33:23 | 显示全部楼层
这是我遇到的一道笔试上机题. 限定程序运行时间是$5s$, 我 当时是用 C++做的, 没留意到 OJ 虽然支持C++提交, 提交却 不支持C++的  vector 和map, 搞的比较糟糕, 没有真正的算法试错环节,没通过.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-5 09:35:53 | 显示全部楼层
wayne 发表于 2017-6-5 09:33
这是我遇到的一道笔试上机题. 限定程序运行时间是$5s$, 我 当时是用 C++做的, 没留意到 OJ 虽然支持C++提交 ...

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

点评

这题目主要是元素比较多. 估计应该还是从 总和不大于1000入手, 时间复杂度是瓶颈  发表于 2017-6-5 09:58
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-5 11:07:45 | 显示全部楼层
是不是要求A,B元素数目相同而且元素和也相同?
解是否存在的判断可以直接用动态规划判断。
我们设C(n,s)为n个元素和为s的方案数目,使用动态规划就可以求出所有的C(n,s).
显然如果所有的C(n,s)都是0或1,那么就无解,如果任意的C(n,s)大于1,就说明存在两组不同的长度为n的子数列,它们的和都是s,去掉公共元素,就得出两个不相交A,B元素数目和元素和都相同。

点评

thanks.  发表于 2017-6-6 10:39
那就应该要容易许多。  发表于 2017-6-5 11:53
是我的集合符号表达误导了,^_^  发表于 2017-6-5 11:38
数目不一定相同.只是要求 元素和相等  发表于 2017-6-5 11:33
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 22:57 , Processed in 0.046346 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表